Computer——树形DP

Computer

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

思路

老师说暴力可过

于是。。。

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
inline void Read(int &x)
{
    x = 0;
    char a = getchar();
    bool f = 0;
    while(a < '0'||a > '9') {if(a == '-') f = 1;a = getchar();}
    while(a >= '0'&&a <= '9') {x = x * 10 + a - '0';a = getchar();}
    if(f) x *= -1;
}
const int MAXN = 10001;
int ans;
bool vis[MAXN];
vector<int> G[MAXN],Road[MAXN];

#define push(x) push_back(x)

inline void dfs(int x,int w)
{
	int i;
	ans = max(ans,w);
	for(i = 0;i < G[x].size();i++)
	{
		int v = G[x][i];
		if(!vis[v])
		{
			vis[v] = 1;
			dfs(v,w + Road[x][i]);
		}
	}
}
int main()
{
	int i,n;
	while(~scanf("%d",&n))
	{
		for(i = 1;i <= n;i++) G[i].clear(),Road[i].clear();
		memset(vis,0,sizeof(vis));
		for(i = 2;i <= n;i++)
		{
			int u,w;
			Read(u),Read(w);
			G[i].push(u),G[u].push(i);
			Road[i].push(w),Road[u].push(w);
		}
		for(i = 1;i <= n;i++)
		{
			memset(vis,0,sizeof(vis));
			vis[i] = 1;
			ans = 0;
			dfs(i,0);
			printf("%d\n",ans);
		}	
	}
    return 0;
}

超简单易懂，居然**$\color{red}\text{TLE}$TLE**了

结合另一道题

又YY出了以下思路

一遍dfs遍历，记录

dis[MAXN]记录最大值（离叶子结点
zg[MAXN]记录次大值（同上

问定点与另一点间最长路径可转化为

求max(dis[x],count(该点所有的父亲))
count()
{
	if 该点在父亲的dis上
		sg + distance(父亲，x)
	else dis + distance(父亲，x)
}

那判断 一点是否在父亲的$\color{blue}\text{dis}$dis上呢？

像我一样的蒟蒻最先是这样搞的

if(dis[father] == dis[x] + distance)

但这组数据会WA

7
1 2
1 1
2 4
1 6
3 3
3 9

答案是

10
12
9
16
16
12
16

但输出了

10
12
9
16
16
——>14
16

是因为

假设x的父亲为$\color{blue}\text{fa}$fa，$\color{blue}\text{fa}$fa的父亲为$\color{blue}\text{father}$father

判断x是否在$\color{blue}\text{father}$father的$\color{blue}\text{dis}$dis上

应为

if(dis[fa] + distance(fa,father) == dis[father]) 
rather than
if(dis[x] + distance(x,father) == dis[father]) 

像

假设每条边权值为1

那$dis[x] + distance(x,father) = 2 &lt; dis[father]$dis[x]+distance(x,father)=2<dis[father]

就会得到ans = 4

但 ans = 3

因为$\color{blue}\text{father}$father至$\color{blue}\text{fa}$fa间不应该可以走两次

而$dis[fa] + distance(fa,father)$dis[fa]+distance(fa,father)就可以避免此种情况

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
inline void Read(int &x)
{
    x = 0;
    char a = getchar();
    bool f = 0;
    while(a < '0'||a > '9') {if(a == '-') f = 1;a = getchar();}
    while(a >= '0'&&a <= '9') {x = x * 10 + a - '0';a = getchar();}
    if(f) x *= -1;
}
const int MAXN = 10001;
vector<int> G[MAXN],Road[MAXN];
int dis[MAXN],zg[MAXN];
bool vis[MAXN];
#define push(x) push_back(x)
inline void dfs(int x)
{
	int i;
	dis[x] = zg[x] = 0;
	for(i = 0;i < G[x].size();i++)
	{
		int v = G[x][i],w = Road[x][i];
		if(!vis[v])
		{
			vis[v] = 1;
			dfs(v);
			G[v].push(w);
			G[v].push(x);
			if(dis[v] + w > dis[x])
			{
				zg[x] = dis[x];
				dis[x] = dis[v] + w;
			}
			else if(dis[v] + w > zg[x])
				zg[x] = dis[v] + w;
		}
	}
}
int main()
{
	int n,i;
	while(~scanf("%d",&n))
	{
		for(i = 1;i <= n;i++) G[i].clear(),Road[i].clear();
		memset(vis,0,sizeof(vis));
		for(i = 2;i <= n;i++)
		{
			int u,w;
			Read(u),Read(w);
			G[i].push(u),G[u].push(i);
			Road[i].push(w),Road[u].push(w);
		}
		vis[1] = 1;
		dfs(1);
		printf("%d\n",dis[1]);
		for(i = 2;i <= n;i++)
		{
			int R = 0,mid = i,fa = G[i][G[i].size() - 1],distance = G[i][G[i].size() - 2];
			int meter = distance;
			while(1)
			{
				if(dis[fa] == dis[mid] + distance)
					R  = max(meter + zg[fa],R);
				else R = max(R,dis[fa] + meter);
				if(fa == 1) break;
				mid = fa;
				distance = G[fa][G[fa].size() - 2],fa = G[fa][G[fa].size() - 1];
				meter += distance;
			}
			printf("%d\n",max(R,dis[i]));
		}
	}
    return 0;
}

然后就~~ 神奇般地$\color{green}\text{AC}$AC了~~