HDU 2196

제목: n대의 컴퓨터가 있는데 그들 사이에는 선이 연결되어 있고 그 사이에는 권한이 있다. 모든 컴퓨터가 어느 컴퓨터로 가는지 물어보는 권한이 가장 크다.
분석: 이 n대 컴퓨터의 관계는 나무 한 그루를 구성할 수 있는데, 문제는 잎 결점의 가장 먼 거리가 얼마냐고 묻는 것이다.
dp(i,0)를 설정하면 i를 자수로 하는 가장 먼 잎사귀 결점 거리를 나타내고, dp(i,1)는 i를 자수로 하는 차원의 잎사귀 결점 거리를 나타내며, dp(i,2)는tree(root)-tree(i)의 가장 먼 거리+dis(root,i), 루트는 i의 부 노드를 나타낸다.
차원거리를 저장하려면 i의 부 노드의 가장 먼 거리가 i를 지나갈 수 있기 때문에 이때는 차원거리의 값을 선택해야 하며 가장 먼 것을 선택할 수 없다.
         

#include 

using namespace std;
const int maxn = 10005;
struct node{
    int v,w;
};

vector com[maxn];
int dp[maxn][3];           //dp[i][0]   i        ，dp[i][1]   i        ,dp[i][2]  i           i       
int visit[maxn];
void dfs1(int u){   //   i             
    visit[u] = 1;
    int max1 = 0,max2 = 0;
    for(int i = 0;i < com[u].size();i++){
        int V = com[u][i].v;
        int W = com[u][i].w;
        if(!visit[V]){
            dfs1(V);
            int tmp = dp[V][0] + W;
            if(tmp >= max1){
                max2 = max1;
                max1 = tmp;
            }
            else if(tmp > max2){
                max2 = tmp;
            }
        }
    }
    dp[u][0] = max1;
    dp[u][1] = max2;
}

void dfs2(int u){
    visit[u] = 1;
    for(int i = 0;i < com[u].size();i++){
        int V = com[u][i].v;
        int W = com[u][i].w;
        dp[V][2] = max(dp[u][2],dp[V][0] + W == dp[u][0] ? dp[u][1]:dp[u][0]) + W;
        if(!visit[V])
            dfs2(V);
    }
}
int main(){
    int n;
    int a,b;
    while(scanf("%d",&n) != EOF){
        for(int i = 1;i <= n;i++)
            com[i].clear();
        for(int i = 2;i <= n;i++){
            scanf("%d%d",&a,&b);
            com[a].push_back(node{i,b});
        }
        memset(dp,0,sizeof(dp));
        memset(visit,0,sizeof(visit));
        dfs1(1);
        memset(visit,0,sizeof(visit));
        dfs2(1);
        for(int i = 1;i <= n;i++){
            printf("%d
",max(dp[i][0],dp[i][2]));
        }
    }
    return 0;
}