树形DP题,做的有些艰难,以前没怎么做过这方面的题目,有些理不清楚,题意很简单,就是给你一些电脑,每两台电脑之间若要连通是需要一定的权值的,把这些电脑按照input连在一起,形成一颗树,问树中每一个节点 到另一个节点(不确定是哪个几点)的距离值中最大距离,
我们知道每一个节点最大值无非来自两个地方,1:来自于他的子树中2;从他父亲节点过来的,但是有个地方要注意,从父节点过来的有可能是直接的,也有可能是父亲的最大距离加上他与父亲的距离,意思就是次长距离加上他与父亲的距离,所以需要两边DFS,第一次从他子树中寻找出最大距离跟次大距离,然后第二次DFS直接对父亲过来的进行更新即可
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::iterator p; // const int N = 10000 + 5; int n; int cnt; int head[N];//头节点 int maxn[N];//该节点下面子树最大距离 int smaxn[N];//该节点下面子树次大距离 int maxid[N];//最大距离所对应的ID int smaxid[N];//次大距离所对应的ID struct Node { int to; int nex; int w; }edge[N*2]; void clear() { cnt= 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w) { edge[cnt].to=v; edge[cnt].w=w; edge[cnt].nex=head[u]; head[u]=cnt++; } //求节点V子树的最大距离,p是v的父亲节点 void dfs1(int u,int p) { maxn[u] = 0; smaxn[u] = 0; for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].to; if(v == p)continue; dfs1(v,u); if(smaxn[u] < maxn[v] + edge[i].w) { smaxn[u] = maxn[v] + edge[i].w; smaxid[u] = v; if(smaxn[u] > maxn[u]) { swap(smaxn[u],maxn[u]); swap(smaxid[u],maxid[u]); } } } } //p是u的父亲节点, void dfs2(int u,int p) { for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].to; if(v == p)continue; if(v == maxid[u]) { if(edge[i].w + smaxn[u] > smaxn[v]) { smaxn[v] = edge[i].w + smaxn[u]; smaxid[v] = u; if(smaxn[v] > maxn[v]) { swap(smaxn[v],maxn[v]); swap(smaxid[v],maxid[v]); } } } else { if(edge[i].w + maxn[u] > smaxn[v]) { smaxn[v] = edge[i].w + maxn[u]; smaxid[v] = u; if(smaxn[v] > maxn[v]) { swap(smaxn[v],maxn[v]); swap(maxid[v],smaxid[v]); } } } dfs2(v,u); } } int main() { while(scanf("%d",&n)==1) { clear(); int v,w; for(int i=2;i<=n;i++) { scanf("%d %d",&v,&w); addedge(i,v,w); addedge(v,i,w); } dfs1(1,-1); dfs2(1,-1); for(int i=1;i<=n;i++) printf("%d\n",maxn[i]); } return EXIT_SUCCESS; }