首先树dp求出一个点的答案

然后再一遍dfs换根(是叫做换根吗..

详见代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define N 500005
#define M 1000006 using namespace std;
inline int read(){
int ret=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while ('0'<=ch&&ch<='9'){
ret=ret*10-48+ch;
ch=getchar();
}
return ret;
} struct edge{
int adj,next,len;
edge(){}
edge(int _adj,int _next,int _len):adj(_adj),next(_next),len(_len){}
} e[M];
int n,g[N],m;
void AddEdge(int w,int u,int v){
e[++m]=edge(v,g[u],w);g[u]=m;
e[++m]=edge(u,g[v],w);g[v]=m;
} ll f[N],h[N],t[N],t0[N];
ll f0[N],h0[N];
int size[N],l[N];
int size0[N];
bool vis[N];
void dfs(int u){
vis[u]=1;
f[u]=l[u];h[u]=2*l[u];t[u]=0;t0[u]=0;
for (int i=g[u];i;i=e[i].next){
int v=e[i].adj;
if (vis[v]) continue;
l[v]=e[i].len;
dfs(v);
f[u]+=h[v];
h[u]+=h[v];
t0[u]=max(t0[u],h[v]-f[v]);
if (t0[u]>t[u]) swap(t0[u],t[u]);
size[u]+=size[v];
}
if (!size[u]) f[u]=h[u]=0;
else f[u]-=t[u];
vis[u]=0;
} ll ans[N];
void solve(int u){
vis[u]=1; f[u]=l[u];h[u]=2*l[u];t[u]=0;t0[u]=0;
for (int i=g[u];i;i=e[i].next){
int v=e[i].adj;
l[v]=e[i].len;
f[u]+=h[v];
h[u]+=h[v];
t0[u]=max(t0[u],h[v]-f[v]);
if (t0[u]>t[u]) swap(t0[u],t[u]);
size[u]+=size[v];
}
if (!size[u]) f[u]=h[u]=0;
else f[u]-=t[u]; ans[u]=f[u];
f0[u]=f[u];h0[u]=h[u];
size0[u]=size[u];
for (int i=g[u];i;i=e[i].next){
int v=e[i].adj;
if (vis[v]) continue;
swap(l[u],l[v]);
if ((size[u]-=size[v])){
h[u]+=(ll)2*l[u]-h[v];
f[u]+=(ll)l[u]-h[v];
if (h[v]-f[v]==t[u]) f[u]+=t[u]-t0[u];
}
else f[u]=h[u]=0; solve(v); f[u]=f0[u];h[u]=h0[u];
size[u]=size0[u];
swap(l[u],l[v]);
}
vis[u]=0;
} int main(){
n=read();int men=read();
for (int i=1;i<n;++i) AddEdge(read(),read(),read());
memset(size,0,sizeof(size));
while (men--) ++size[read()];
memset(vis,0,sizeof(vis));
l[1]=0;
dfs(1);
solve(1);
for (int i=1;i<=n;++i) printf("%lld\n",ans[i]);
return 0;
}

  

05-03 21:30