2017.9.17 kamp 思考记录

一开始读错题了，以为只有一个座位、

首先，通过从一个点出发，它走过的路径是一个半环，如果把半环补上，那所有的环上的点答案都一样

对于不在环上的点，它一定是沿树上路径到达环上的点

所以剩下的问题就是求每个点的最远点

于是就可以用树dp的思想来统计

max1【i】表示i这个节点到子树的最远点及距离

max2【i】表示i这个节点到子树的次远点及距离

为什么要统计次远点？因为不能折返，所以离散后不一样的选择只有两种——都选最远，如果在一个子树内就选次远

还要注意父节点也会往下传信息，取个max就好

主要就是容斥的思想，不是去主动决策找点，而是全算出来之后选择删哪个

似乎我的码全场最长？。。。

码（又长又蠢）：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 600005
#define ll long long
int f[N],xia[N],zhong[N<<1],a,b,c,qi,hou[N<<1],tot,n,k;
ll lin,max1[N][3],max2[N][3],ans[N],v[N<<1];
bool you[N],lj[N],vis[N];
void jian(int a,int b,int c)
{
	++tot,hou[tot]=xia[a],xia[a]=tot,zhong[tot]=b,v[tot]=c;
}
void jia(int a,int b,int c)
{
	jian(a,b,c);
	jian(b,a,c);
}
void dp(int o,int fa)
{
	if(you[o])f[o]++;
int i;
for(i=xia[o];i!=-1;i=hou[i])
{
int nd=zhong[i];
if(nd==fa)continue;
dp(nd,o);
f[o]+=f[nd];	
}		
}
void dfs(int o)
{
	int i;
	lj[o]=1;
	if(you[o]&&f[o]==1)return;
	vis[o]=1;
	for(i=xia[o];i!=-1;i=hou[i])
	{
		int nd=zhong[i];
		if(vis[nd]||f[nd]==0)continue;
		lin+=2*v[i];
		dfs(nd);		
	}	
}
void dfs2(int o,int fa,int dis)
{
	int i;
	ans[o]=dis+lin;
	for(i=xia[o];i!=-1;i=hou[i])
	{
  int nd=zhong[i];
  	  if(nd==fa)continue;
  	  if(lj[nd]==0)dfs2(nd,o,dis+v[i]*2);
  	  else dfs2(nd,o,dis);
	}	
}
void dp2(int o,int fa)
{     
if(you[o])
{
	if(max1[o][0]<0)
	{
		max1[o][0]=0;
		max1[o][1]=o;
	}else if(max2[o][0]<0)
	{
		max2[o][0]=0;
		max2[o][1]=o;
	}
}
    int i;
    for(i=xia[o];i!=-1;i=hou[i])
	{
		int nd=zhong[i];
		if(nd==fa)continue;
		dp2(nd,o);
		if(max1[nd][0]+v[i]>max1[o][0])
		{   
		    max2[o][0]=max1[o][0];
		    max2[o][1]=max1[o][1];
			max1[o][0]=max1[nd][0]+v[i];
			max1[o][1]=nd;
		}else
		{
		if(max1[nd][0]+v[i]>max2[o][0])
		{
			max2[o][0]=max1[nd][0]+v[i];
			max2[o][1]=nd;
		}	
		}
	}
}
void dfs3(int o,int fa,int dis)
{
	int i;
	if(dis>max1[o][0])
	{
		max2[o][0]=max1[o][0];
		max2[o][1]=max1[o][1];
		 max1[o][0]=dis;
		 max1[o][1]=0;
	}else if(dis>max2[o][0])
	{
		max2[o][0]=dis;
		max2[o][1]=0;
	}
	ans[o]-=max1[o][0];
	for(i=xia[o];i!=-1;i=hou[i])
	{
	int nd=zhong[i];
	if(nd==fa)continue;
	if(nd==max1[o][1])
	{
    dfs3(nd,o,max(dis+v[i],max2[o][0]+v[i]));	
	}else 	    dfs3(nd,o,max(dis+v[i],max1[o][0]+v[i]));	
			
	}		
}
int main()
{
	memset(max1,-0x7f,sizeof(max1));
	memset(max2,-0x7f,sizeof(max2));
	memset(xia,-1,sizeof(xia));
	int i;
	scanf("%d%d",&n,&k);
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
			jia(a,b,c);
	}
	for(i=1;i<=k;i++)
	{
		scanf("%d",&a);
		you[a]=1;
		qi=a;
	}
dp(qi,0);
dfs(qi);
dfs2(qi,0,0);
dp2(qi,0);
dfs3(qi,0,0);
for(i=1;i<=n;i++)printf("%lld\n",ans[i]);	
}