题意:
实验室里原先有一台电脑 (编号为 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]));
- }
- }
来源: http://www.bubuko.com/infodetail-3494127.html