NKOJ 2698 Nicole的博客 （动态树+最小生成树）

发表于 |
字数统计: 1,258字 | 阅读时长 ≈ 7min

P2698【动态树】Nicole的博客

问题描述

给你一个由N个节点M条带权边构成的无向简单图，然后进行Q次操作：
·1 x y ：询问一条连接x,y的路径，使路径上权值最大的边权值最小；
·2 x y ：删除原本连接x,y的边，保证这条边存在。
对每次询问，输出路径上权值最大的边的权值。

输入格式

第一行三个数N,M,Q
接下来M行每行三个数x,y,z，表示有一条连接x,y的边，权值为z
接下来Q行，每行k,x,y，表示一次操作

输出格式

对每次询问输出一行

样例输入

4 4 3
1 2 2
2 3 3
3 4 2
1 4 2
1 1 4
2 1 4
1 1 4

样例输出

2
3

提示

1<=N<=100000
1<=M<=1000000
1<=Q<=100000
1<=x,y<=N
1<=z<=109
保证任意时刻整个图连通

由询问可知，显然维护一颗最小生成树，然后考虑操作二，删边，不好操作。
考虑离线，显然倒序讨论，那么删边变成加边，用LCT维护这颗最小生成树，直接搞就好。
关于处理边权，将边变成点，然后往两个端点连边即可转化成点权。

代码：

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 2000005
using namespace std;
struct node{int x,y,z,id;bool f;}edge[N];
bool cmp1(node a,node b)
{return a.z<b.z;}
bool cmp2(node a,node b)
{
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
int n,m,q,top,S[N],F[N],Hash[N];
int ty[N],A[N],B[N],Ans[N];
int ls[N],rs[N],fa[N],Max[N],id[N],v[N],rev[N];
int GM(int x,int y,int z)
{
	if(x>=y&&x>=z)return x;
	if(y>=z)return y;
	return z;
}
bool Isroot(int x)
{return ls[fa[x]]!=x&&rs[fa[x]]!=x;}
void MT(int p)
{
	Max[p]=GM(v[p],Max[ls[p]],Max[rs[p]]);
	if(Max[p]==v[p])id[p]=p;
	else if(Max[p]==Max[ls[p]])id[p]=id[ls[p]];
	else id[p]=id[rs[p]];
}
void PD(int p)
{
	if(rev[p])
	{
		swap(ls[p],rs[p]);
		rev[ls[p]]^=1;
		rev[rs[p]]^=1;
		rev[p]^=1;
	}
}
void Zig(int x)
{
	int y=fa[x],z=fa[y];
	if(!Isroot(y))y==ls[z]?ls[z]=x:rs[z]=x;fa[x]=z;
	ls[y]=rs[x];fa[rs[x]]=y;
	rs[x]=y;fa[y]=x;
	MT(y);MT(x);
}
void Zag(int x)
{
	int y=fa[x],z=fa[y];
	if(!Isroot(y))y==ls[z]?ls[z]=x:rs[z]=x;fa[x]=z;
	rs[y]=ls[x];fa[ls[x]]=y;
	ls[x]=y;fa[y]=x;
	MT(y);MT(x);
}
void Splay(int x)
{
	int i,y,z;
	S[++top]=x;
	for(i=x;!Isroot(i);i=fa[i])S[++top]=fa[i];
	while(top)PD(S[top--]);
	while(!Isroot(x))
	{
		y=fa[x];z=fa[y];
		if(!Isroot(y))
		{
			if(y==ls[z])x==ls[y]?(Zig(y),Zig(x)):(Zag(x),Zig(x));
			else x==rs[y]?(Zag(y),Zag(x)):(Zig(x),Zag(x));
		}
		else x==ls[y]?Zig(x):Zag(x);
	}
}
void Access(int x)
{
	for(int t=0;x;x=fa[x])
	{
		Splay(x);
		rs[x]=t;
		MT(x);t=x;
	}
}
void Makeroot(int x)
{
	Access(x);
	Splay(x);
	rev[x]^=1;
}
void Link(int x,int y)
{
	Makeroot(x);
	fa[x]=y;
}
void Cut(int x,int y)
{
	Makeroot(x);
	Access(y);
	Splay(y);
	ls[y]=fa[x]=0;
}
int GF(int x)
{
	if(F[x]!=x)F[x]=GF(F[x]);
	return F[x];
}
void Kruscal()
{
	int i=1,cnt=0,x,y,fx,fy;
	while(cnt<n-1)
	{
		if(edge[i].f){i++;continue;}
		x=GF(edge[i].x);
		y=GF(edge[i].y);
		if(x!=y)
		{
			F[x]=y;
			cnt++;
			Link(edge[i].id,edge[i].x);
			Link(edge[i].id,edge[i].y);
		}
		i++;
	}
}
int main()
{
	int i,j,k,x,y,z;node tmp;
	scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
		if(edge[i].y<edge[i].x)swap(edge[i].x,edge[i].y);
		edge[i].id=n+i;v[n+i]=edge[i].z;
	}
	sort(edge+1,edge+m+1,cmp2);
	for(i=1;i<=q;i++)
	{
		scanf("%d%d%d",&ty[i],&A[i],&B[i]);
		if(ty[i]==1)continue;
		if(A[i]>B[i])swap(A[i],B[i]);
		tmp.x=A[i];tmp.y=B[i];
		j=lower_bound(edge+1,edge+m+1,tmp,cmp2)-edge;
		edge[j].f=1;
	}
	for(i=1;i<=m;i++)Hash[edge[i].id]=i;
	for(i=1;i<=n;i++)F[i]=i;
	sort(edge+1,edge+m+1,cmp1);
	Kruscal();
	sort(edge+1,edge+m+1,cmp2);
	for(i=q;i>=1;i--)
	{
		if(ty[i]==1)
		{
			Makeroot(A[i]);
			Access(B[i]);
			Splay(B[i]);
			Ans[i]=Max[B[i]];
		}
		else
		{
			tmp.x=A[i];tmp.y=B[i];
			j=lower_bound(edge+1,edge+m+1,tmp,cmp2)-edge;
			Makeroot(A[i]);
			Access(B[i]);
			Splay(B[i]);
			if(edge[j].z<Max[B[i]])
			{
				k=Hash[id[B[i]]];
				Cut(edge[k].x,edge[k].id);
				Cut(edge[k].y,edge[k].id);
				Link(edge[j].x,edge[j].id);
				Link(edge[j].y,edge[j].id);
			}
		}
	}
	for(i=1;i<=q;i++)if(ty[i]==1)printf("%d\n",Ans[i]);
}