「福建wc2014」路径权值 - Kruskal重构树

题目大意

给定一个带权树，树上任意两点间的路径权值$d(x,y)$定义为$x$,$y$这两个点之间路径上的最小值，树上任意一点$x$的权值定义为这个点到树上其他所有点的路径权值和，即$\sum_i(d(x,i)), 1\le i\le n$，现求树上一点，使得这个点的权值最大，输出这个值。

---

题目分析

考虑每个点显然是不可做的，因此考虑每条边对答案的贡献。
如果一条边是权值最小的，如图：

那么这条边$x\leftrightarrow y$对结点$u$的贡献就是$size\times w[x\leftrightarrow y]$。
但是原图中只有一条权值最小的，其他的怎么处理呢？
这就涉及到一个技巧：Kruskal重构树。
Kruskal重构树可以处理最小生成树边权最值问题。
我们用Kruskal算法时，新建一个结点作为合并集合的root，将原来两个集合连上去。
发现重构树了过后有以下性质：

• 新树是一棵二叉树
• 原树路径边权最值与新树路径点权最值相同
• 子结点的权值$\ge$或$\le$父亲结点权值
• 原树中路径边权的最值等于新树上LCA的点权

那么在重构树后，每一条边的贡献变成了新树中每一个点的贡献。
我们发现，对于一个新树的新点，他的权值一定是最小的（性质4），那么我们只需要计算新树上新点的子树的贡献（不考虑父亲结点，因为父亲结点的权值更小，会被计算）。
因为对于一个新点，他的其中一棵子树中结点增加的贡献都相同，相当于子树加减，可以通过Dfs序树状数组完成。
另外因为这是一棵二叉树，所以说只需要处理两次贡献即可，代码实现非常方便。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=200005;
struct Edge {
	int from,to,dist;
	Edge(int u=0,int v=0,int d=0):from(u),to(v),dist(d) {}
	bool operator < (const Edge& b) const {
		return dist>b.dist;
	}
};
vector<Edge>edge;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
	edges[x].push_back(y);
}
int First[maxn],Last[maxn],Size[maxn],father[maxn],Value[maxn],n,q,cnt,step=0;
void Dfs(int Now) {
	First[Now]=++step;
	Size[Now]=Now<=n;
	for(auto &Next:edges[Now]) {
		Dfs(Next);
		Size[Now]+=Size[Next];
	}
	Last[Now]=step;
}
struct BIT {
	int c[maxn];
	#define Lowbit(x) x&(-x)
	void add(int x,int v) {
		for(int i=x; i<=2*n; i+=Lowbit(i))c[i]+=v;
	}
	int sum(int x) {
		int ans=0;
		for(int i=x; i>=1; i-=Lowbit(i))ans+=c[i];
		return ans;
	}
} bit;
void Update(int x,int y) {
	bit.add(First[x],y);
	bit.add(Last[x]+1,-y);
}
void Clear() {
	for(int i=1; i<=2*n; i++)edges[i].clear();
	edge.clear();
	for(int i=1; i<=2*n; i++)father[i]=i;
	step=0;
	memset(bit.c,0,sizeof(bit.c));
}
int Get_Father(int x) {
	if(father[x]==x)return x;
	else return father[x]=Get_Father(father[x]);
}
int main() {
	q=Get_Int();
	for(int t=1; t<=q; t++) {
		cnt=n=Get_Int();
		Clear();
		for(int i=1; i<n; i++) {
			int x=Get_Int(),y=Get_Int(),v=Get_Int();
			edge.push_back(Edge(x,y,v));
		}
		sort(edge.begin(),edge.end());
		for(auto &e:edge) {
			int fx=Get_Father(e.from),fy=Get_Father(e.to);
			Value[++cnt]=e.dist;
			father[fx]=father[fy]=cnt;
			AddEdge(cnt,fx);
			AddEdge(cnt,fy);
		}
		Dfs(cnt);
		for(int i=n+1; i<=cnt; i++) {
			Update(edges[i][0],Size[edges[i][1]]*Value[i]);
			Update(edges[i][1],Size[edges[i][0]]*Value[i]);
		}
		int ans=0;
		for(int i=1; i<=n; i++)ans=max(ans,bit.sum(First[i]));
		printf("Case %d: %d\n",t,ans);
	}
	return 0;
}