bzoj 3743: [Coci2015]Kamp【树形dp】

两遍dfs一遍向下，一边向上，分别记录子树内人数a，当前点到所有点的距离b，最大值c和次大值d，最大值子树p

然后答案是2b-c

#include<iostream>

#include<cstdio>

using namespace std;

const int N=1000005;

int n,m,h[N],cnt,p[N];

long long a[N],b[N],c[N],d[N];

bool v[N];

struct qwe

{

	int ne,to,va;

}e[N];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v,int w)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	e[cnt].va=w;

	h[u]=cnt;

}

void dfs1(int u,int fa)

{

	if(v[u])

		a[u]=1;

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to!=fa)

		{

			dfs1(e[i].to,u);

			a[u]+=a[e[i].to],b[u]+=b[e[i].to];

			if(a[e[i].to])

			{

				b[u]+=e[i].va;

				if(c[e[i].to]+e[i].va>=c[u])

					d[u]=c[u],c[u]=c[e[i].to]+e[i].va,p[u]=e[i].to;

				else if(c[e[i].to]+e[i].va>=d[u])

					d[u]=c[e[i].to]+e[i].va;

			}

		}

}

void dfs2(int u,int fa)

{

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to!=fa)

		{

			b[e[i].to]=b[u];

			if(a[e[i].to]==0)

				b[e[i].to]+=e[i].va;

			if(a[e[i].to]==m)

				b[e[i].to]-=e[i].va;

			long long nw=(e[i].to==p[u]?d[u]:c[u])+e[i].va;

			if(nw>=c[e[i].to])

				d[e[i].to]=c[e[i].to],c[e[i].to]=nw,p[e[i].to]=0;

			else if(nw>=d[e[i].to])

				d[e[i].to]=nw;

			dfs2(e[i].to,u);

		}

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<n;i++)

	{

		int x=read(),y=read(),z=read();

		add(x,y,z),add(y,x,z);

	}

	for(int i=1;i<=m;i++)

	{

		int x=read();

		v[x]=1;

	}

	dfs1(1,0);

	dfs2(1,0);

	for(int i=1;i<=n;i++)

		printf("%lld\n",b[i]*2-c[i]);

	return 0;

}