求出一棵树中离每个点最远的点。。 典型的树形DP。。老题了。。看程序吧。。 Java太难写这种题目了。。只好用c++了。。
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int,int> pi;
struct edge
{
int t,c;
edge(int _t,int _c):t(_t),c(_c){}
};
const int maxn=10000;
pi ch[maxn];
int f[maxn];
vector<edge> E[maxn];
typedef vector<edge>::iterator it;
void add_edge(int s,int t,int c)
{
E[s].push_back(edge(t,c));
E[t].push_back(edge(s,c));
}
void Renew(pi&o,int x)
{
if(o.second<x)
{
o.second=x;
if(o.first<o.second)
swap(o.first,o.second);
}
}
void Renew(int&x,int c)
{
x=max(x,c);
}
void dfsch(int x,int fa)
{
ch[x]=pi(0,0);
for(it i=E[x].begin();i!=E[x].end();i++)
if(i->t!=fa)
{
dfsch(i->t,x);
Renew(ch[x],ch[i->t].first+i->c);
}
}
void dfsf(int x,int fa)
{
for(it i=E[x].begin();i!=E[x].end();i++)
if(i->t!=fa)
{
Renew(f[i->t],f[x]+i->c);
if(ch[x].first==ch[i->t].first+i->c)
Renew(f[i->t],ch[x].second+i->c);
else
Renew(f[i->t],ch[x].first+i->c);
dfsf(i->t,x);
}
}
int n;
void init()
{
scanf("%d",&n);
for(int s=1,t,c;s<n;s++)
{
scanf("%d %d",&t,&c);
add_edge(s,t-1,c);
}
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();f[0]=0;
dfsch(0,-1);
dfsf(0,-1);
for(int i=0;i<n;i++)
printf("%dn",max(ch[i].first,f[i]));
}