「福建wc2014」路径权值 - Kruskal重构树 | Bill Yang's Blog
0%

「福建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序树状数组完成。
另外因为这是一棵二叉树,所以说只需要处理两次贡献即可,代码实现非常方便。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#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;
}
姥爷们赏瓶冰阔落吧~