题意:
给一棵树, 求出每一点到树上其他点的最远距离
思路:
1我们先考虑一个点到其子树中的点的最远距离
定义 1.dp[i][0] 是以 i 号节点为跟到其子树的最远距离
2.dp[i][1] 是以 i 号节点为跟到其子树的次远距离 (为什么维护这个后面可以知道)
3.son[i] 是以 i 号节点为根的的子树中距离 i 最远的儿子的编号
这样可以通过第一次 dfs 来的到
2现在再来考虑最远距离要通过其父亲
定义 1.dp[i][2] 为通过 i 的父亲能到达的最远距离
如果 i 的父亲 fa 到其子树的最远路径中包含 w(fa,i), 那么 dp[i][2]=max(dp[fa][1]+w,dp[fa][2]+w)
否则就为: dp[i][2]=max(dp[fa][0]+w,dp[fa][2]+w)
最后, 每个点的最远距离就为 max(dp[i][0],dp[i][2])
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<vector>
- using namespace std;
- typedef long long ll;
- const int maxn=30005;
- ll dp[maxn][3],son[maxn],tot;
- int head[maxn],ver[maxn],nxt[maxn],edge[maxn];
- void add_edge(int u,int v,int w)
- {
- edge[++tot]=w;
- ver[tot]=v;
- nxt[tot]=head[u];
- head[u]=tot;
- }
- void dfs1(int u,int fa)
- {
- for(int i=head[u];i;i=nxt[i]){
- int y=ver[i];
- int w=edge[i];
- if(y==fa) continue;
- dfs1(y,u);
- if(dp[u][0]<=dp[y][0]+w){
- dp[u][1]=dp[u][0];
- dp[u][0]=dp[y][0]+w;
- son[u]=y;
- }
- else if(dp[y][0]+w>=dp[u][1]) dp[u][1]=dp[y][0]+w;
- else if(dp[y][1]+w>dp[u][1]) dp[u][1]=dp[y][1]+w;
- }
- }
- void dfs2(int x,int fa)
- {
- for(int i=head[x];i;i=nxt[i]){
- int y=ver[i];
- if(y==fa) continue;
- int w=edge[i];
- if(son[x]==y)
- dp[y][2]=max(dp[x][1]+w,dp[x][2]+w);
- else dp[y][2]=max(dp[x][0]+w,dp[x][2]+w);
- dfs2(y,x);
- }
- }
- int main()
- {
- int n,u,v;
- while(scanf("%d",&n)!=EOF){
- tot=0;
- memset(dp,0,sizeof(dp));
- memset(son,0,sizeof(dp));
- memset(head,0,sizeof(head));
- for(int i=2;i<=n;i++){
- scanf("%d%d",&u,&v);
- add_edge(i,u,v);
- add_edge(u,i,v);
- }
- dfs1(1,1);
- dfs2(1,1);
- for(int i=1;i<=n;i++)
- printf("%lld\n",max(dp[i][0],dp[i][2]));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3393511.html