【NOIP2018模拟赛2018.10.3】到不了
题目分析
被一个假题解骗了改了一下午。
在线和离线都可以。
先将无根数的根连一个0根做一下lca。
对于每次修改,用并查集维护现在的根,再重新做一下倍增修改。
对于每次查询,直接找深度较深的即可了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define out(x) print(x)
const int MAXN = 1e5 + 5;
int f[MAXN][21];
int dep[MAXN],rt[MAXN],root[MAXN];
int size[MAXN];
int head[MAXN*2],cnt = 0;
struct node {
int next,to;
} e[MAXN*2];
void add(int u,int v) {
e[++cnt].next = head[u],e[cnt].to = v,head[u] = cnt;
e[++cnt].next = head[v],e[cnt].to = u,head[v] = cnt;
}
int n,m,q,E;
void rebuild(int x,int fr) {
for(int i = 1; i <= 20; i++) f[x][i] = f[f[x][i-1]][i-1];
for(int i = head[x]; i; i = e[i].next) {
int to = e[i].to;
if(to == fr) continue;
dep[to] = dep[x] + 1;
f[to][0] = x;
rebuild(to,x);
}
}
void dfs(int x,int fr) {
f[x][0] = fr;
for(int i = head[x]; i; i = e[i].next) {
int to = e[i].to;
if(to == fr) continue;
dep[to] = dep[x] + 1;
dfs(to,x);
size[x] += size[to];
}
}
int get(int x) {
for(int i = 20; i >= 0; i--) if(f[x][i]) x = f[x][i];
return x;
}
int lca(int x,int y) {
if(dep[x] < dep[y]) swap(x,y);
for(int i = 20; i >= 0; i--)
if(dep[x] - (1 << i) >= dep[y])
x = f[x][i];
if(x == y) return x;
for(int i = 20; i >= 0; i--)
if(f[x][i] != f[y][i])
x = f[x][i],y = f[y][i];
return f[x][0];
}
int main() {
cin>>n>>m;
for(int i = 1; i <= m; i++) cin>>rt[i];
int e;
cin>>e;
for(int i = 1; i <= n-m; i++) {
int x,y;
cin>>x>>y;
add(x,y);
}
for(int i = 1; i <= n; i++) size[i] = 1;
for(int i = 1; i <= m; i++) {
dep[rt[i]] = 1;
dfs(rt[i],0);
}
for(int j = 1; j <= 20; j++)
for(int i = 1; i <= n; i++)
f[i][j] = f[f[i][j-1]][j-1];
for(int i = 1; i <= n; i++) {
int o = get(i);
if(o) root[i] = o;
else root[i] = i;
}
cin>>q;
for(int i = 1; i <= q; i++) {
int o,u,v;
cin>>o>>u>>v;
if(o == 1) {
int x = get(u),y = get(v);
if(x == y) continue;
if(size[x] > size[y]) {
f[v][0] = u;
size[x] += size[y];
dep[v] = dep[u] + 1;
root[y] = root[x];
add(u,v);
rebuild(v,u);
} else {
f[u][0] = v;
size[y] += size[x];
dep[u] = dep[v] + 1;
root[y] = root[x];
add(u,v);
rebuild(u,v);
}
} else {
int a = u;
int b = v;
if(get(a) != get(b)) {
cout << "orzorz" << endl;
continue;
} else {
int c = get(a);
int a = lca(u,v);
int b = lca(root[c],v);
if(dep[a] < dep[b]) a = b;
b = lca(root[c],u);
if(dep[a] < dep[b]) a = b;
cout<<a<<endl;
}
}
}
return 0;
}