51nod 1737 配對 樹的重心

傳送門：51nod1737

題意：中文題。

思路：畫圖可以得知對于每一條邊，它對答案的貢獻一定不超過它兩端子樹的大小的較小值，并且使答案最大的每條路徑都應該是經過重心的，是以題目可以轉化為求所有點到重心的權值和。（直接按發現的規律求也可以）。

代碼：

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
const int MAXN = 100010;
int pre[MAXN], sz[MAXN];
int cnt, max_sz = inf;
int n, rt;
ll ans = 0;
struct node{
	int v, w, next;
	node(int _v = 0, int _w = 0, int _next = 0) : v(_v), w(_w), next(_next) {}
} mp[MAXN << 1];
void init()
{
	memset(pre, -1, sizeof(pre));
	cnt = 0;
}
void add(int u, int v, int w)
{
	mp[cnt] = node(v, w, pre[u]); pre[u] = cnt++;
}
void dfs(int u, int fa)
{
	sz[u] = 1;
	int tmp = 0;
	for(int i = pre[u]; ~i; i = mp[i].next)
	{
		int v = mp[i].v;
		if(v == fa) continue;
		dfs(v, u);
		sz[u] += sz[v];
		tmp = max(tmp, sz[v]);
	}
	tmp = max(tmp, n - sz[u]);
	if(tmp < max_sz)
	{
		max_sz = tmp;
		rt = u;
	}
}
void get_ans(int u, int fa, ll dis)
{
	ans += dis;
	for(int i = pre[u]; ~i; i = mp[i].next)
	{
		int v = mp[i].v;
		if(v == fa) continue;
		get_ans(v, u, dis + mp[i].w);
	}
}
int main()
{
	int u, v, w;
	init();
	scanf("%d", &n);
	for(int i = 1; i < n; i++)
	{
		scanf("%d %d %d", &u, &v, &w);
		add(u, v, w);
		add(v, u, w);
	}
	dfs(1, -1);
	get_ans(rt, -1, 0);
	cout << ans << endl;
 	return 0;
}