P6419 [COCI2014-2015#1] Kamp(换根树形DP)
nofind
·
·
题解
题意
显然是换根，先考虑以1为根进行第一次dfs：
设f_x表示从x出发到子树中每个标记点后返回x的最小距离，dis_{0,x}表示x到子树中的标记点的最远距离。
显然答案为f_1-dis_{0,1}。
考虑换根：
我们为了换根，需要再维护dis_{1,x}表示x到子树中的标记点的次远距离，且保证最远和次远不在同一棵子树中。
我们考虑x\not =1的答案包含x的子树与x的子树外，因此设g_x表示x子树外的答案，up_x表示x到子树外标记点的最远距离。
转移方程都好写，可以看代码。
code:
```
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+10;
int n,m,cnt_edge;
int head[maxn],a[maxn],size[maxn],f[maxn],g[maxn],up[maxn];
int dis[2][maxn];
struct edge{int to,nxt,dis;}e[maxn<<1];
inline int read()
{
char c=getchar();int res=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
return res*f;
}
inline void add_edge(int u,int v,int w)
{
e[++cnt_edge].nxt=head[u];
head[u]=cnt_edge;
e[cnt_edge].to=v;
e[cnt_edge].dis=w;
}
void dfs1(int x,int fa)
{
size[x]=a[x];
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa)continue;
dfs1(y,x);size[x]+=size[y];
if(size[y])
{
f[x]+=f[y]+e[i].dis*2;
if(dis[0][y]+e[i].dis>dis[0][x])dis[1][x]=dis[0][x],dis[0][x]=dis[0][y]+e[i].dis;
else if(dis[0][y]+e[i].dis>dis[1][x])dis[1][x]=dis[0][y]+e[i].dis;
}
}
}
void dfs2(int x,int fa)
{
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa)continue;
if(m-size[y])
{
g[y]=g[x]+f[x]-f[y];
if(!size[y])g[y]+=2*e[i].dis;
if(dis[0][x]==dis[0][y]+e[i].dis)up[y]=max(up[x],dis[1][x])+e[i].dis;
else up[y]=max(up[x],dis[0][x])+e[i].dis;
}
dfs2(y,x);
}
}
signed main()
{
n=read(),m=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read(),w=read();
add_edge(u,v,w),add_edge(v,u,w);
}
for(int i=1;i<=m;i++)a[read()]++;
dfs1(1,0);dfs2(1,0);
for(int i=1;i<=n;i++)printf("%lld\n",f[i]+g[i]-max(dis[0][i],up[i]));
return 0;
}
```