学海泛舟

hdoj 2196 Computer 题解

发表于 | 分类于 |

原题

传送门

题目大意

给定一颗n个结点的树，求出每个结点到离它最远的点的距离

分析

虽然每条边都有权值，但其本质并没有变化。
这个问题与求树的直径基本相似。
很容易想清楚，树上任意一个结点的最远点必然是树的直径的两个端点中的一个。
那么，这个问题就只需要三次dfs就能解决了。
第一个dfs，找到其中一个端点。
第二个dfs，以找到的一个端点为起点，找到另一个，并且顺便更新所有点到起点的距离。
第三个dfs，以另一个端点为起点，更新所有点的最远距离。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
const int maxn=10010;
struct Edge
{
    int to,next,w;
}edge[maxn<<1];
int head[maxn];
int dist[maxn];
int tot;
void addedge(int u,int v,int w)
{
    edge[tot].to=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}
int flag;
int tdis;
void dfs(int root,int pre,int dis)
{
    dist[root]=max(dist[root],dis);
    if(dis>tdis)
    {
        flag=root;
        tdis=dis;
    }
    for(int i=head[root];~i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==pre) continue;
        dfs(v,root,dis+edge[i].w);
    }
}
void solve()
{
    tdis=0;
    dfs(flag,-1,0);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        tot=0;
        memset(head,-1,sizeof head);
        memset(dist,0,sizeof dist);
        int v,len;
        for(int i=2;i<=n;++i)
        {
            scanf("%d %d",&v,&len);
            addedge(i,v,len);
            addedge(v,i,len);
        }
        flag=1;
        for(int i=0;i<3;++i)
        {
            solve();
        }
        for(int i=1;i<=n;++i)
        {
            printf("%d\n",dist[i]);
        }
    }
	return 0;
}