hdu4118 樹形dp

 

Problem Description Nowadays, people have many ways to save money on accommodation when they are on vacation.
One of these ways is exchanging houses with other people.
Here is a group of N people who want to travel around the world. They live in different cities, so they can travel to some other people's city and use someone's house temporary. Now they want to make a plan that choose a destination for each person. There are 2 rules should be satisfied:
1. All the people should go to one of the other people's city.
2. Two of them never go to the same city, because they are not willing to share a house.
They want to maximize the sum of all people's travel distance. The travel distance of a person is the distance between the city he lives in and the city he travels to. These N cities have N - 1 highways connecting them. The travelers always choose the shortest path when traveling.
Given the highways' information, it is your job to find the best plan, that maximum the total travel distance of all people.
Input The first line of input contains one integer T(1 <= T <= 10), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(2 <= N <= 10⁵), representing the number of cities.
Then the followingN-1 lines each contains three integersX, Y,Z(1 <= X, Y <= N, 1 <= Z <= 10⁶), means that there is a highway between city X and city Y , and length of that highway.
You can assume all the cities are connected and the highways are bi-directional.
Output For each test case in the input, print one line: Case #X: Y, where X is the test case number (starting with 1) and Y represents the largest total travel distance of all people.
Sample Input

2
4
1 2 3
2 3 2
4 3 2
6
1 2 3
2 3 4
2 4 1
4 5 8
5 6 5

Sample Output

Case #1: 18
Case #2: 62

 

 

/**
hdu 4118 樹形dp
題目大意：一棵n節點的樹，每個節點有一個人，每個人離開自己的位置到另一個位置，每個位置只能有一個人，問這n個人移動距離和的最大值。
解題思路：（轉）如果找出樹的重心就可以把樹分成左右兩部分，左邊的點跟右邊的點交換位置，兩點交換位置的距離=兩點到根節點的距離之和的2倍，
           總距離就是所有點到根節點距離之和的2倍了，當時猶豫了一下，如果節點數是奇數的話，這樣是不是根節點沒換位置呢？後來一想，
           這種交換位置每個點走的路徑都經過根節點，根節點跟任意一個點交換一下就可以了，答案還是一樣的。
           樹形DP：我們可以統計沒條邊被走了多少次，一條邊可以把點分為左右兩部分，兩部分中點數較少的一部分都要離開自己的位置去另一邊，
           這條邊被走了min(son[u](右邊點數),son[v])*2次，點數多的一部分有的位置是沒變的，但是我們這樣把每條邊都操作一遍後，所有點的位置都變了。
注：遞歸dfs會爆內存。
*/
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn=100005;

struct note
{
    int v,w,next;
} edge[maxn*2];

int head[maxn],ip;
int n,vis[maxn],num[maxn],sta[maxn];
LL ans;

void init()
{
    memset(head,-1,sizeof(head));
    ip=0;
}

void addedge(int u,int v,int w)
{
    edge[ip].v=v,edge[ip].w=w,edge[ip].next=head[u],head[u]=ip++;
}

///遞歸形式會超出內存
void dfs(int u,int pre)
{
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==pre)continue;
        dfs(v,u);
        num[u]+=num[v];
        ans+=(LL)edge[i].w*2*min(num[v],n-num[v]);
    }
    num[u]++;
}

///用棧實現非遞歸形式
void dfs1(int u)
{
    memset(vis,0,sizeof(vis));
    int top=0;
    sta[top++]=u;
    vis[u]=1;
    while(top>0)
    {
        bool flag=1;
        int t=sta[top-1];
        for(int i=head[t]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;
            if(vis[v])continue;
            sta[top++]=v;
            vis[v]=1;
            flag=0;
        }
        if(flag==0)continue;
        for(int i=head[t]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;
            if(num[v]!=0)
            {
                num[t]+=num[v];
                ans+=(LL)edge[i].w*2*min(num[v],n-num[v]);
            }
        }
        num[t]++;
        top--;
    }
}

int main()
{
    int T,tt=0;
    scanf(%d,&T);
    while(T--)
    {
        scanf(%d,&n);
        init();
        for(int i=1; i