Description：

给出一棵树上每条边的权值和修改代价，求最小的修改代价使得树的直径减小。

$1\le N \le 100000$

Solution：

先把树的直径求出来，然后找直径的中心，具体找的方法是如果有一个点到直径一个端点距离大于等于直径的一半，再往这个端点走一条边距离就小于直径的一半了，那么这个点就是中点。

发现所有的直径一定交于中点，将所有的直径取出来一定是一棵树，在这棵树上做树上动归，求出把以 $k$ 为根的直径树直径减少的最小代价。方程为 $g[k]=min(\sum g[son],val(k,fa))$

发现中点不一定恰好位于直径的中间，可能是一条长的和很多条短的，不可能有多条长的，把他们分别放到两个数组里，则最后结果可能是断掉所有短的，或断掉那一条长的，取 $min$ 即可，还有可能是所有出边都一样长，只要保留一个即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

#define INF 0x3f3f3f3f

using namespace std;

int n;

#define MAXN 100010

struct edge

{

	int to,nxt,t,p;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b,int t,int p)

{

	e[edgenum].to = b;e[edgenum].t = t;e[edgenum].p = p;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].t = t;e[edgenum].p = p;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

void init()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	int a,b,c,d;

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

	{

		scanf("%d%d%d%d",&a,&b,&c,&d);

		add(a,b,c,d);

	}

	return;

}

int d[MAXN],pre[MAXN];

bool v[MAXN];

int bfs(int s)

{

	queue<int> q;

	q.push(s);

	memset(d,-1,sizeof(d));

	memset(v,0,sizeof(v));

	d[s] = 0;

	v[s] = true;

	pre[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(!v[e[i].to] && d[e[i].to] < d[k] + e[i].t)

			{

				v[e[i].to] = true;

				d[e[i].to] = d[k] + e[i].t;

				q.push(e[i].to);

				pre[e[i].to] = i;

			}

		}

	}

	int k = 1;

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

	{

		if(d[i] > d[k])k = i;

	}

	return k;

}

int root;

int len;

void center()

{

	int a,b;

	a = bfs(1);

	b = bfs(a);

	len = d[b];

	for(int i = b;i != a;i = e[pre[i] ^ 1].to)

	{

		if(2 * d[e[pre[i] ^ 1].to] < len && 2 * d[i] >= len)

		{

			root = i;

		}

	}

	return;

}

int f[MAXN],fa[MAXN];

void dfs(int k)

{

	v[k] = true;

	f[k] = 0;

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(!v[e[i].to])

		{

			pre[e[i].to] = i;

			fa[e[i].to] = i;

			dfs(e[i].to);

			f[k] = max(f[k],f[e[i].to] + e[i].t);

		}

	}

	v[k] = false;

	return;

}

int g[MAXN];

int dp(int k)

{

	v[k] = true;

	g[k] = 0;

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(!v[e[i].to] && f[k] == f[e[i].to] + e[i].t)

		{

			g[k] += dp(e[i].to);

		}

	}

	if(g[k] == 0)g[k] = INF;

	g[k] = min(g[k],e[fa[k]].p);

	v[k] = false;

	return g[k];

}

int a[MAXN],tota = 0,b[MAXN],totb = 0;

void solve()

{

	memset(v,0,sizeof(v));

	memset(fa,-1,sizeof(fa));

	dfs(root);

	for(int i = lin[root];i != -1;i = e[i].nxt)

	{

		if(f[e[i].to] + e[i].t == d[root])

		{

			a[++tota] = e[i].to;

		}

		else if(f[e[i].to] + e[i].t == len - d[root])

		{

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

		}

	}

	memset(g,0,sizeof(g));

	v[root] = true;

	int now,temp,ans = 0;

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

	{

		now = dp(a[i]);

		ans += now;

		if(now > temp)

		{

			temp = now;

		}

	}

	now = 0;

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

	{

		now += dp(b[i]);

	}

	if(len != d[root] && temp > now)

	{

		ans -= temp - now;

	}

	cout << ans << endl;

	return;

}

int main()

{

	init();

	center();

	solve();

	return 0;

}