kruskal重构树

Kruskal重构树

第二次学了。
大致思路就是在最小生成树加边的时候，把每条边也设一个点，和他连着的两个点连边。由于最小生成树的贪心，感觉很像哈夫曼树，有性质是经过的边的长度（已经转化为点权）越向上越大/越小，取决于生成树的排序。那就可以通过倍增找不经过长度超过x的边所能走到的所有点，实际上是一直往上跳的那个子树。

		for (int i=1;i<=n;i++) bel[i]=i,top[i]=i;
		int num=n;
		for (int i=1;i<=m;i++)
		{
			int f1=find(edges[i].u),f2=find(edges[i].v);
			if (f1==f2) continue;
			++num;
			bel[f1]=f2;
			addedge(num,top[f1],edges[i].a);
			addedge(num,top[f2],edges[i].a);
			top[f2]=num;
		}
1
2
3
4
5
6
7
8
9
10
11
12

bel是并查集的fa，top是这一坨联通块现在的最上面的那个代表边的点的编号。fa正常合并，每次把top改成“新建的那个代表边的点”，再加边就向这个点连边即可。

题：NOI2018归程
题目链接
大意：每条边有一个海拔，多组询问，每次询问给出$v,p$，海拔高于$p$的边没有长度，问从$v$号点走到$1$号点的最短路。
思路：根据重构树的性质，做最大生成树，他的重构树保证越向上海拔越小，从$v$倍增向上跳，一直跳到海拔小于$p$，那么实际上能“免费”走到的点就应该是能向上跳的最顶上的点的那个子树。维护子树mindis即可。

#include
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	ll f=1,sum=0;char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=500010;
const int MAXM=1000010;
struct Node{
	int u,v,a,l;
	bool operator < (const Node b) const {return a>b.a;}
}edges[MAXM];
int bel[MAXN],top[MAXN];
int find(int x)
{
	if (bel[x]!=x) bel[x]=find(bel[x]);
	return bel[x];
}
struct edge{
	int next,to,val;
}e[MAXM*2];
int head[3*MAXN],cnt;
void addedge(int u,int v,int w)
{
	e[++cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].val=w;
	head[u]=cnt;
}
int dis[MAXN];
priority_queue <pa,vector<pa>,greater<pa> > q;
bool vis[MAXN];
void Dijkstra(int n)
{
	for (int i=1;i<=n;i++) dis[i]=INT_MAX,vis[i]=0;
	dis[1]=0;
	q.push(mp(0,1));
	while (!q.empty())
	{
		int x=q.top().se;
		q.pop();
		if (vis[x]) continue;
		vis[x]=1;
		for (int i=head[x];i;i=e[i].next)
		{
			int v=e[i].to;
			if (dis[v]>dis[x]+e[i].val) dis[v]=dis[x]+e[i].val,q.push(mp(dis[v],v));
		}
	}
}
const int LOG=25;
int f[MAXN][LOG],g[MAXN][LOG];
int mn[MAXN];
void dfs(int x,int n)
{
	if (x<=n) mn[x]=dis[x];
	else mn[x]=INT_MAX;
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		g[v][0]=e[i].val;
		f[v][0]=x;
		dfs(v,n);
		mn[x]=min(mn[x],mn[v]);
	}
}
int main()
{
	int T=read();
	while (T--)
	{
		memset(head,0,sizeof(head));
		cnt=0;
		int n=read(),m=read();
		for (int i=1;i<=m;i++) 
		{
			edges[i].u=read(),edges[i].v=read(),edges[i].l=read(),edges[i].a=read();
			addedge(edges[i].u,edges[i].v,edges[i].l);
			addedge(edges[i].v,edges[i].u,edges[i].l);
		}
		Dijkstra(n);
		memset(head,0,sizeof(head));
		cnt=0;
		sort(edges+1,edges+1+m);
		for (int i=1;i<=n;i++) bel[i]=i,top[i]=i;
		int num=n;
		for (int i=1;i<=m;i++)
		{
			int f1=find(edges[i].u),f2=find(edges[i].v);
			if (f1==f2) continue;
			++num;
			bel[f1]=f2;
			addedge(num,top[f1],edges[i].a);
			addedge(num,top[f2],edges[i].a);
			top[f2]=num;
		}
		dfs(num,n);
		f[num][0]=num;
		for (int j=1;j<LOG;j++) for (int i=1;i<=num;i++) f[i][j]=f[f[i][j-1]][j-1];
		for (int j=1;j<LOG;j++) for (int i=1;i<=num;i++) g[i][j]=g[f[i][j-1]][j-1];
		// for (int i=1;i<=num;i++,cout<
		int q=read(),k=read(),s=read();
		int lastans=0;
		while (q--)
		{
			int v0=read(),p0=read();
			int v=(1ll*v0+1ll*k*lastans-1)%n+1;
			int p=(1ll*p0+1ll*k*lastans)%(s+1);
			// cout<
			for (int i=LOG-1;i>=0;i--)
				if (g[v][i]>p) v=f[v][i];//cout<
			// cout<
			lastans=mn[v]; 
			cout<<lastans<<'\n';
		}
	}
	return 0;
}
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

题：洛谷P7834 [ONTAK2010] Peaks 加强版
题目链接
大意：无向图，强制在线多组询问从$u$点出发不经过权值$>x$的边，能走到的点的点权第$k$大是多少。
思路：重构树+倍增向上跳找到子树根，转化为求子树根的第$k$大，经典dfs序上主席树。

#include
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	ll f=1,sum=0;char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=300010;
const int MAXM=1000010;
struct edge{
	int next,to;
}e[MAXM*4];
int head[MAXN],cnt;
void addedge(int u,int v)
{
	e[++cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
struct Node{
	int u,v,w;
	bool operator < (const Node b) const {return w<b.w;}
}edges[MAXM];
int a[MAXN],fa[MAXN],top[MAXN],val[MAXN];
int find(int x)
{
	if (fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
const int LOG=25;
int sz[MAXN],f[MAXN][LOG],g[MAXN][LOG],l[MAXN],r[MAXN];
int tots;
struct Point{
	int lch,rch,val;
}tr[MAXN*LOG];
int root[MAXN],treenum;
int modify(int pre,int left,int right,int x)
{
	int now=++treenum;
	if (left==right)
	{
		tr[now].lch=tr[now].rch=0;
		tr[now].val=tr[pre].val+1;
		return now;
	}
	int mid=(left+right)>>1;
	if (x<=mid)
	{
		tr[now].lch=modify(tr[pre].lch,left,mid,x);
		tr[now].rch=tr[pre].rch;
	}
	else
	{
		tr[now].lch=tr[pre].lch;
		tr[now].rch=modify(tr[pre].rch,mid+1,right,x);
	}
	tr[now].val=tr[tr[now].lch].val+tr[tr[now].rch].val;
	return now;
}
int query(int root1,int root2,int left,int right,int k)
{
	if (left==right) return left;
	int mid=(left+right)>>1;
	if (tr[tr[root2].lch].val-tr[tr[root1].lch].val>=k) return query(tr[root1].lch,tr[root2].lch,left,mid,k);
	else return query(tr[root1].rch,tr[root2].rch,mid+1,right,k-tr[tr[root2].lch].val+tr[tr[root1].lch].val);
}
void dfs_order(int x,int n)
{
	if (x<=n)
	{
		l[x]=r[x]=++tots;
		root[tots]=modify(root[tots-1],1,n,a[x]);
		return ;
	}
	int i=head[x];
	dfs_order(e[i].to,n);
	l[x]=l[e[i].to];
	i=e[i].next;
	dfs_order(e[i].to,n);
	r[x]=r[e[i].to];
}
void dfs(int x)
{
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		f[v][0]=x,g[v][0]=val[x];
		dfs(v);
		sz[x]+=sz[v];
	}
	if (!sz[x]) sz[x]=1;
}
vector <int> vals;
int main()
{
	int n=read(),m=read(),q=read();
	for (int i=1;i<=n;i++) a[i]=read(),vals.push_back(a[i]);
	sort(vals.begin(),vals.end());
	int newsize=unique(vals.begin(),vals.end())-vals.begin();
	vals.resize(newsize);
	for (int i=1;i<=n;i++) a[i]=lower_bound(vals.begin(),vals.end(),a[i])-vals.begin()+1;
	for (int i=1;i<=m;i++) edges[i].u=read(),edges[i].v=read(),edges[i].w=read();
	sort(edges+1,edges+1+m);
	for (int i=1;i<=n;i++) fa[i]=i,top[i]=i;
	int num=n;
	for (int i=1;i<=m;i++)
	{
		int f1=find(edges[i].u),f2=find(edges[i].v);
		if (f1==f2) continue;
		++num;
		fa[f1]=f2;
		addedge(num,top[f1]),addedge(num,top[f2]);
		// cout<
		val[num]=edges[i].w;
		top[f2]=num;
	}
	dfs(num);
	f[num][0]=num,g[num][0]=val[num];
	// for (int i=1;i<=num;i++) cout<
	for (int j=1;j<LOG;j++) for (int i=1;i<=num;i++) f[i][j]=f[f[i][j-1]][j-1];
	for (int j=1;j<LOG;j++) for (int i=1;i<=num;i++) g[i][j]=g[f[i][j-1]][j-1];
	// for (int i=1;i<=num;i++,cout<
	int lstans=0;
	dfs_order(num,n);
	while (q--)
	{
		int _u=read(),_x=read(),_k=read();
		int u=(_u^lstans)%n+1,x=_x^lstans,k=(_k^lstans)%n+1;
		for (int j=LOG-1;j>=0;j--) if (g[u][j]<=x) u=f[u][j];
		if (sz[u]<k)
		{
			cout<<"-1\n";
			lstans=0;
			continue;
		}
		k=sz[u]-k+1;
		int ret=query(root[l[u]-1],root[r[u]],1,n,k);
		lstans=vals[ret-1];
		cout<<lstans<<'\n';
	}
	return 0;
}
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