题目

题解

  这道题就是看每一个点到其他点的距离和是多少。数据范围告诉我们 绝 对 不 能 用暴力求解（TLE自动机.jpg)。因为本题满足树的性质且很明显答案之间有某种联系（真实原因：看题目）所以考虑DP求解。
  分析题目可知，所求的值就是以第 i i i号节点为根的树上根到每一个点的距离和。
  画图后可以发现对于每一个节点，可以假设第 i i i号节点到其他点的距离和为 d e p [ i ] dep[i] dep[i]。对于某一个 i i i的子节点 j j j来说，显然 d e p [ i ] dep[i] dep[i]与 d e p [ j ] dep[j] dep[j]之间只有 i i i到 j j j的路统计数量不同（对于j的子树，无论在 i i i的子树中和在 j j j的子树中的统计数量肯定是一样的¹，对于树中其他的点来说，这些点的循环次数也没有变化）且统计数量的差异就是少统计了 j j j的子树大小个，多统计了剩余节点个数个。设 j j j号点的子树大小为 s i z e [ j ] size[j] size[j]可推出DP方程式 d e p [ j ] = d e p [ i ] − s i z e [ i ] × l e n [ i ] [ j ] + ( n − s i z e [ j ] ) × l e n [ i ] [ j ] dep [j] = dep[i]-size[i] \times len[i][j] + (n - size[j]) \times len[i][j] dep[j]=dep[i]−size[i]×len[i][j]+(n−size[j])×len[i][j]
  因此可以先用dfs搜索出以节点 1 1 1为根的 d e p dep dep值再用刚才求出的DP方程式进行换根操作就可以求出答案了。

code

#include<cstdio>
#include<algorithm>
#define Size 100010

using namespace std;

struct line
{
	int to;
	int next;
	long long value;
}L[Size * 2];

int k[Size];

int n , top , hand[Size] , Siz[Size] , fat[Size] ;
long long dep[Size];

void add(int x , int y , long long z)
{
	L[top].to = y;
	L[top].next = hand[x];
	L[top].value = z;
	hand[x] = top ++;
}
//链式前向星

void size(int x , int last)
{
	Siz[x] = 1;
	fat[x] = last;
	for(int i = hand[x] ; i != -1 ; i = L[i].next)
	{
		int y = L[i].to;
		if(fat[x] == y)
			continue;
		size(y , x);
		Siz[x] += Siz[y];
		dep[1] += Siz[y] * L[i].value;
	}
}
//处理 1 根

void ans(int x)
{
	for(int i = hand[x] ; i != -1 ; i = L[i].next)
	{
		int y = L[i].to;
		if(fat[x] == y)
			continue;
		dep[y] = dep[x] + (n - Siz[y] - Siz[y]) * 1ll * L[i].value;
		ans(y);
	}
}
//换根

int main()
{
	for(int i = 0 ; i < Size ; i ++)
	{
		hand[i] = -1;
	}
	scanf("%d" , &n);
	for(int i = 0 ; i < n - 1 ; i ++ )
	{
		int x , y;
		long long z;
		scanf("%d%d%lld" , &x , &y , &z);
		add(x , y , z);
		add(y , x , z);
	}
	size(1 , 0);
	ans(1);
	for(int i = 1 ; i <= n ; i ++)
	{
		printf("%lld\n" , dep[i]);
	}
	return 0;
}

欢迎各路大佬吐槽……

---

1. 可以画图看看。 ↩︎