Kruskal重构树学习笔记
为做这道题,特意去学了一波Kruskal重构树。
以下写写学习心得:
首先像Kruskal一样按权值排序,
不过将Kruskal生成树的并查集合并操作改为了新建点,为合并的两点的父亲,点权为加入的边的权值的操作作者不要脸地剽图了
变为:
有一些性质:
1.二叉树。
2.点权大根堆(Kruskal从小到大的排序,从小到大则反之)
3.两点间的最大距离为LCA的权值--->两点能否通过边权<=k的边互达:倍增跳到LCA是否小于等于k
例题1:
路径权值
Description
给定一个带权树,树上任意两点间的路径权值d(x,y)定义为x,y这两个点之间路径上的最小值,树上任意一点x的权值定义为这个点到树上其他所有点的路径权值和,即\(\sum_{i=1}^{n} d(x,i)\),现求树上一点,使得这个点的权值最大,输出这个值。
Input
首先输入一个整数Q,接着每组数据首先输入一个整数 n(1≤n≤100000),表示该组数1据中树的点的个数。
接下来n−1行,每行三个整数 x,y,s(1≤x,y≤n,1≤s≤1000),表示编号为x的节点和编号为y的节点之间存在一条权值为s的边,树上每个点的编号为1~n
Output
对于每组数据,首先输出数据编号,然后输出树上的点的最大权值,具体格式见输出样例。
Sample Input
2
4
1 2 2
2 4 1
2 3 1
4
1 2 1
2 4 1
2 3 1
Sample Output
Case 1: 4
Case 2: 3
上文说的这道题就是例题2,
下面给出代码:
int getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}
bool merge(int u,int v,int w){
u=getf(u),v=getf(v);
if(u==v) return false;
++tot,f[u]=f[v]=f[tot]=tot,add(tot,u),add(tot,v);
fa[u][0]=fa[v][0]=tot,maxx[u][0]=maxx[v][0]=w;
return true;
}
for(int i=1;i<=20;++i) fa[x][i]=fa[fa[x][i-1]][i-1],maxx[x][i]=max(maxx[x][i-1],maxx[fa[x][i-1]][i-1]);