[GDOI2017] 取石子游戏(LCA)
题面
给出一棵树，每个点都有一个权值。对于每个节点，求去掉该节点的子树后，剩下所有节点的权值MEX(最小的没有出现的非负整数。)
分析
用权值线段树合并乱搞显然是可行的，但细节很多且需要卡常。
我们考虑所有权值为(i)的节点对答案的影响。求所有节点的LCA,那么对于从LCA向上到根的路径上的节点,去掉子树后的部分中一定没有值(i).那么值(i)就可能成为它们的MEX。
因此按权值从小到大，每次求出权值为(i)的节点的LCA,然后暴力往上跳,把没有被更新过的节点的答案设为(i),否则已经更新过的节点答案一定比(i)小,可以停止。当找到第一个没有节点出现的权值时,这个权值可以用来更新整棵树的MEX,直接扫一遍更新答案即可。
容易发现更新答案的复杂度是(O(n))的，再加上求LCA,复杂度(O(n log n))
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define maxn 1000000
using namespace std;
template<typename T> void qread(T &x) {
x=0;
T sign=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') sign=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
x=x*sign;
}
template<typename T> void qprint(T x) {
if(x<0) {
putchar('-');
qprint(-x);
} else if(x==0) {
putchar('0');
return;
} else {
if(x>=10) qprint(x/10);
putchar('0'+x%10);
}
}
int cas,n,m;
struct edge {
int from;
int to;
int next;
} E[maxn*2+5];
int esz=1;
int head[maxn+5];
void add_edge(int u,int v) {
esz++;
E[esz].from=u;
E[esz].to=v;
E[esz].next=head[u];
head[u]=esz;
}
int a[maxn+5];
vector<int>pos[maxn+5];
int ans[maxn+5];
int fa[maxn+5],son[maxn+5],sz[maxn+5],top[maxn+5],deep[maxn+5];
void dfs1(int x,int f) {
fa[x]=f;
sz[x]=1;
son[x]=0;
deep[x]=deep[f]+1;
for(int i=head[x]; i; i=E[i].next) {
int y=E[i].to;
if(y!=f) {
dfs1(y,x);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}
}
void dfs2(int x,int t) {
top[x]=t;
if(son[x]) dfs2(son[x],t);
for(int i=head[x]; i; i=E[i].next) {
int y=E[i].to;
if(y!=fa[x]&&y!=son[x]) {
dfs2(y,y);
}
}
}
int lca(int x,int y) {
while(top[x]!=top[y]) {
if(deep[top[x]]<deep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(deep[x]<deep[y]) return x;
else return y;
}
void clear() {
memset(E,0,sizeof(E));
esz=1;
memset(head,0,sizeof(head));
memset(a,0,sizeof(a));
memset(fa,0,sizeof(fa));
memset(son,0,sizeof(son));
memset(sz,0,sizeof(sz));
memset(top,0,sizeof(top));
memset(deep,0,sizeof(deep));
}
int main() {
#ifdef LOCAL
freopen("game9.in","r",stdin);
freopen("game9.ans","w",stdout);
#endif
int u,v;
qread(cas);
while(cas--) {
clear();
qread(n);
qread(m);
for(int i=1; i<=n; i++) qread(a[i]);
cerr<<"ok"<<endl;
for(int i=1; i<=m; i++) {
qread(u);
qread(v);
add_edge(u,v);
add_edge(v,u);
}
cerr<<"ok"<<endl;
for(int i=0; i<=n; i++) pos[i].clear();
for(int i=1; i<=n; i++) ans[i]=-1;
for(int i=1; i<=n; i++) pos[a[i]].push_back(i);
cerr<<"ok"<<endl;
dfs1(1,0);
dfs2(1,1);
cerr<<"ok"<<endl;
for(int i=0; i<=n; i++) {
if(pos[i].empty()) {
for(int j=1; j<=n; j++) if(ans[j]==-1) ans[j]=i;
break;//比i更大的无意义
}
int lc=0;
for(int j=0; j<(int)pos[i].size(); j++) {
if(lc==0) lc=pos[i][j];
else lc=lca(lc,pos[i][j]);
}
//除了lc子树外,剩下的部分都没有值i
for(int x=lc; x&&ans[x]==-1; x=fa[x]) ans[x]=i; //更新mex
}
for(int i=1; i<=n; i++) {
if(ans[i]==-1) ans[i]=0;
qprint(ans[i]);
putchar(' ');
}
putchar('
');
}
// system("pause");
}
/*
1
6 5
5 2 1 0 3 1
1 2
1 3
1 4
3 5
2 6
*/