SGU 149 Computer Network 树状DP求单点到树的最大距离

传送门;Computer Network

题目大意

这个题目主要是输入理解了好长时间，不安正常的顺序出牌呀！！ 第一行输入的是点的数量，下面的N-1行(从第二行开始)，第一个数和第几行这个数相连，也就是和i相连。第二个数是权值！

解题思路

解题思路，这个和求树的直径是异曲同工的！第一个DFS中的dp[i][0]表示第i个节点到子树的最大距离，dp[i][1]表示第i个节点到子树的次长距离！然后第二个DFS中的dp[i][0]表示第i个节点到整个树的最长距离，dp[i][1]表示第i个节点到整个树的次长距离！

AC代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 10000 + 5; const int INF = 0x3f3f3f3f; int dp[MAXN][3],head[MAXN],e; struct Edge{ int v,nxt,w; }E[MAXN<<2]; void init() { e = 0; memset(head,-1,sizeof head); } void add(int u,int v,int w) { E[e].v = v; E[e].w = w; E[e].nxt = head[u]; head[u] = e++; } void DFS(int u,int pre) { for(int i=head[u];~i;i=E[i].nxt) { int v = E[i].v; if(v==pre)continue; DFS(v,u); int tmp = dp[v][0]+E[i].w; if(tmp>dp[u][0]) swap(tmp,dp[u][0]); if(tmp>dp[u][1]) dp[u][1] = tmp; } } void _DFS(int u,int pre) { for(int i=head[u];~i;i=E[i].nxt) { int v = E[i].v,w=E[i].w; if(v==pre) continue; int tmp; if(dp[v][0]+w==dp[u][0]) tmp = w+dp[u][1]; else tmp = w+dp[u][0]; if(tmp>dp[v][0]) swap(tmp,dp[v][0]); if(tmp>dp[v][1]) dp[v][1] = tmp; _DFS(v,u); } } int main() { int N; int u,w; while(~scanf("%d",&N)) { init(); for(int i=2;i<=N;i++){ scanf("%d%d",&u,&w); add(i,u,w);add(u,i,w); } DFS(1,-1); _DFS(1,-1); for(int i=1;i<=N;i++) printf("%d\n",dp[i][0]); } return 0; }