luoguP1131

。。。这道题我也不知道咋\(A\)的。

思路：

\(anst\) 距离 \(s\) 的最长距离，\(ansp\) 某一节点到祖先所有边的权值和这些些加过的权值和

先求出到\(s\)距离最长的点，其他点通过使用道具增加到这个点的长度。对于每一个节点，记录一个它的子节点到它的距离最长的点（距离\(dis[u]\)）。在\(u\)到它父亲的边上加\(anst-ansp-dis[u]\),\(ans\)也加上\(anst-ansp-dis[u]\)。

。。。解释得不太清楚

#include<iostream>

#include<cstdio>

#include<cstring>

#define LL long long

using namespace std;

const int N = 500005;

int head[N],n,tot,s,m[N];

struct edge{

	int node,next,data;

}e[N<<1];

long long ans,anst,dis[N];

void add(int x,int y,int z)

{

	e[++tot].node=y; e[tot].data=z;

	e[tot].next=head[x]; head[x]=tot;

}

inline int read()

{

	int ans=0,w=1;

	char c=getchar();

	while((c<'0'||c>'9')&&c!='-') c=getchar();

	if(c=='-') { w=-1; c=getchar(); }

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

	{ ans=ans*10+c-'0'; c=getchar(); }

	return ans*w;

}

void dfs(int u,int fa)

{

	for(int i=head[u];i;i=e[i].next)

	{

		int v=e[i].node;

		if(v==fa) continue;

		dfs(v,u);

		if(dis[v]+e[i].data>dis[u])

		 dis[u]=dis[v]+e[i].data,m[u]=v;

	}

}

void dfs1(int u,int fa,LL ansp)

{

	ans+=(anst-dis[u]-ansp),ansp+=(anst-dis[u]-ansp);

	for(int i=head[u];i;i=e[i].next)

	{

		int v=e[i].node;

		if(v==fa) continue;

		dfs1(v,u,ansp+e[i].data);

	}

}

int main()

{

//	memset(dis,0x7f,sizeof(dis));

	n=read(); s=read();

	int x,y,z;

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

	{

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

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

	}

	dfs(s,0);

	anst=dis[s];

	dfs1(s,0,0);

	printf("%lld\n",ans);

	return 0;

}

巴特西

luoguP1131

luoguP1131

最新文章

热门文章