HDU2196 Computer(树形DP)

系统管理员 2021-09-16 04:52 363阅读 0赞

Computer  
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 33823 Accepted Submission(s): 5161

Problem Description  
A school bought the first computer some time ago(so this computer’s id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.

Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.

Input  
Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.

Output  
For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).

Sample Input  
5  
1 1  
2 1  
3 1  
1 1

Sample Output  
3  
2  
3  
4  
4  
一道经典的树形DP  
**题意**  
求每个节点能到达的最长距离  
**思路**  
1.一个节点第一步假如往它的儿子节点走，那么它肯定只能一直往它的儿子方向走。  
2.一个节点第一步假如往它的父亲节点走，那么它就有两种选择，但绝对不能再走回来。  
设f\[u\]  f \[ u \] 为第一步往它的**儿子节点**走的最长距离。  
设g\[u\]  g \[ u \] 为第一步往它的**父亲节点**走的最长距离。  
设p\[u\]  p \[ u \] 为u  u 的父亲。  
w(x,y) w ( x , y )表示x-y这条边的权值  
1.f\[u\]=max(f\[v\]\+w(u,v))  f \[ u \] = m a x ( f \[ v \] + w ( u , v ) )  v是u的儿子  v 是 u 的 儿 子   
2.g\[u\]=w(u,p\[u\])\+max(g\[p\[u\]\],f\[v\]\+w(p\[u\],v))  g \[ u \] = w ( u , p \[ u \] ) + m a x ( g \[ p \[ u \] \] , f \[ v \] + w ( p \[ u \] , v ) )  v是u的兄弟，显然不能考虑u本身  v 是 u 的 兄 弟 ， 显 然 不 能 考 虑 u 本 身   
我们第一次dfs可以求出f\[x\]  f \[ x \] ，第二次dfs可以求出g\[x\]  g \[ x \]   
**注意点**  
1.f\[x\]  f \[ x \]  是从下往上求的，所以是先求下面，再更新上面的，而求g\[x\]  g \[ x \] 则不同，你需要更新它上面的节点，才能求下面的节点  
2.很显然，求g\[x\]  g \[ x \] 时你不能考虑它本身，因为重复了，你也不能考虑它的祖父节点，因为它已经更新了，包括在它之前的g\[x\]  g \[ x \] 了

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){
       if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    
    const int maxn = 10000 + 10;
    vector<PII> e[maxn];
    int f[maxn];
    int g[maxn];
    int p[maxn];
    
    int dfs1(int u,int pre)
    {
        for(auto & v : e[u])
        {
            if(v.first != pre)
            {
                f[u] = max(f[u],v.second + dfs1(v.first,p[v.first] = u));//这里注意要更新父亲节点
            }
        }
        return f[u];
    }
    
    void dfs2(int u,int pre)
    {
        int t = 0;
        g[u] = g[pre];
        for(auto &v : e[pre])//找它的兄弟
        {
            if(v.first == p[pre])//祖父节点，包括在g[pre]里了
                continue;
            if(v.first == u) t = v.second;//它本身，最后要加上的所以记录一下
            else
                g[u] = max(g[u],f[v.first]+v.second);
        }
        g[u] += t;
        for(auto &v : e[u])//它是从上往下更新的
        {
            if(v.first != pre)
                dfs2(v.first,u);
        }
    }
    
    int n;
    int main(int argc, char const *argv[])
    {
        while(scanf("%d",&n)!=EOF)
        {
            rep(i,1,n+1)
            {
                p[i] = i;
                f[i] = 0;
                g[i] = 0;
                e[i].clear();
            }
            rep(i,2,n+1)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                e[x].push_back(make_pair(i,y));
                e[i].push_back(make_pair(x,y));
            }
            dfs1(1,0);
            dfs2(1,0);
            rep(i,1,n+1)
            {
                printf("%d\n",max(f[i],g[i]));
            }
        }
        return 0;
    }