HDU 2196 Computer

题目大意

% 　　给定一棵边带权树，你需要输出对于每个点而言，距离它最远的点和它的距离。 　　数据范围　$1⩽n⩽10^4,1⩽w_{(u,v)}⩽10^9$

题解

% 　　无根树不好考虑，先钦定一个点为根节点。 % 　　考虑树形dp，定义 $down[u]$ 表示点 $u$ 的子树中距离点 $u$ 最远的点到点 $u$ 的距离。则有 $$down[u]=\underset{v\in son(u)}{\max }\{down[v]+1\}$$

% 　　求出后，我们考虑求出子树外的答案，定义 $up[u]$ 表示不考虑 $u$ 点的子树，其余点到点 $u$ 的最远的点到点 $u$ 的距离，由于已经求出了 $down$，这里的转移也不难。 $$up[u]=\max \{\begin{array}{l}up[fa(u)]+w_{(u,fa(u))}\\ \underset{t\in son(fa(u)),t\ne u}{\max }down[t]+w_{(t,fa(u))}+w_{(fa(u),u)}\end{array}$$

% 　　上面那条是通过父亲直接转移，下面那条通过其他儿子通过父亲连到自己的。 　　考虑如何线性求出下面哪条式子的值。若我们假设 $fa(u)$ 的第 $k$ 个儿子为 $son(fa(u))[k]$，则定义 $$\begin{gathered} pre[k]=\underset{p=1}{\overset{k}{\max }}{w}_{(son(fa(u)[p],fa(u)))}+down[son(fa(u))[p]], \\ fix[k]=\underset{p=k}{\overset{|son(fa(u))|}{\max }}{w}_{(son(fa(u)[p],fa(u)))}+down[son(fa(u))[p]] \end{gathered}$$

% 　　若 $u$ 是 $fa(u)$ 的第 $s$ 个儿子，则转移可以写成 $$up[u]=\max \{\begin{array}{l}up[fa(u)]+w_{(u,fa(u))}\\ suf[s-1]+fix[s+1]+w_{(fa(u),u)}\end{array}$$

% 　　如此，我们考虑在访问 $fa(u)$ 时，将 $fa(u)$ 的每个儿子都算出来，如此递推，最后的答案便是 $\max (up[u],down[u])$。详见代码（变量和上述定义基本一致）。时间复杂度 $\Theta (n)$。

代码

#include<bits/stdc++.h> using namespace std; #define int long long #define maxn 10010 struct edge{ int v,w,next; }edges[maxn<<1]; int n,head[maxn],cnt=0; void ins(int u,int v,int w){ edges[++cnt]=(edge){v,w,head[u]}; head[u]=cnt; } int down[maxn]; void dfs(int u,int fa=-1){ down[u]=0; for(int i=head[u];i;i=edges[i].next){ int v=edges[i].v; if(v==fa) continue; dfs(v,u); down[u]=max(down[u],down[v]+edges[i].w); } } int up[maxn],pre[maxn],suf[maxn],fix[maxn],son[maxn],wei[maxn]; void redfs(int u,int fa=-1){ int cnt=0; for(int i=head[u];i;i=edges[i].next){ int v=edges[i].v; if(v==fa) continue; up[v]=max(up[v],up[u]+edges[i].w); son[++cnt]=v; wei[cnt]=edges[i].w; pre[cnt]=max(pre[cnt-1],down[v]+edges[i].w); } fix[cnt+1]=0; for(int i=cnt;i>0;i--) fix[i]=max(fix[i+1],down[son[i]]+wei[i]); for(int i=1;i<=cnt;i++) up[son[i]]=max(up[son[i]],wei[i]+max(pre[i-1],fix[i+1])); for(int i=head[u];i;i=edges[i].next){ int v=edges[i].v; if(v==fa) continue; redfs(v,u); } } signed main(){ while(~scanf("%lld",&n)){ memset(down,0,sizeof down); memset(pre,0,sizeof pre); memset(suf,0,sizeof suf); memset(fix,0,sizeof fix); memset(head,cnt=0,sizeof head); memset(up,0,sizeof up); for(int i=2,v,w;i<=n;i++){ scanf("%lld%lld",&v,&w); ins(i,v,w);ins(v,i,w); } dfs(1); redfs(1); for(int i=1;i<=n;i++) printf("%lld\n",max(up[i],down[i])); } return 0; }