题意:
实验室里原先有一台电脑(编号为1),最近绿名DD为又为实验室py了赞助,购置了N-1台电脑,编号为2到N。每台电脑都用网线连接到一台先前安装的电脑上。但是队内大佬担心网速太慢,问他第i台电脑到其他电脑的最大网线长度,但是贪玩的绿名DD沉迷城市天际线忘了计算,请你帮帮他。
题解:
nmd太难了,我先跪下了
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=1e4+100; struct node { int u,v,w,next; }edge[maxn*2]; int tol; int head[maxn*2]; void addedge (int u,int v,int w) { edge[tol].u=u; edge[tol].v=v; edge[tol].w=w; edge[tol].next=head[u]; head[u]=tol++; } int dp[maxn][3]; //分别为正向最大,正向次大,反向最大 int l[maxn]; int dfs (int u,int pre) { //返回u的正向最大距离 if (dp[u][0]>=0) return dp[u][0]; dp[u][0]=dp[u][1]=dp[u][2]=l[u]=0; for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if (v==pre) continue; if (dp[u][0]<dfs(v,u)+edge[i].w) { l[u]=v; dp[u][1]=max(dp[u][1],dp[u][0]); dp[u][0]=dfs(v,u)+edge[i].w; } else if (dp[u][1]<dfs(v,u)+edge[i].w) dp[u][1]=max(dp[u][1],dfs(v,u)+edge[i].w); } return dp[u][0]; } void dfs_again (int u,int pre) { for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if (v==pre) continue; if (v==l[u]) dp[v][2]=max(dp[u][2],dp[u][1])+edge[i].w; else dp[v][2]=max(dp[u][2],dp[u][0])+edge[i].w; dfs_again(v,u); } } int main () { int N; while (~scanf("%d",&N)) { tol=0; memset(head,-1,sizeof(head)); memset(dp,-1,sizeof(dp)); memset(l,-1,sizeof(l)); for (int i=2;i<=N;i++) { int v,w; scanf("%d%d",&v,&w); addedge(i,v,w); addedge(v,i,w); } dfs(1,-1); dfs_again(1,-1); for (int i=1;i<=N;i++) printf("%d\n",max(dp[i][0],dp[i][2])); } }