正題

題目鏈接:https://gmoj.net/senior/#main/show/5097

---

題目大意

$n$個(gè)點(diǎn)的一棵樹(shù)，每個(gè)節(jié)點(diǎn)有權(quán)值。對(duì)于每個(gè)點(diǎn)求樹(shù)上所有權(quán)值去除掉他的子樹(shù)的權(quán)值后的$mex$值。

---

解題思路

對(duì)于一個(gè)權(quán)值$w$，權(quán)值為$w$的所有點(diǎn)的$LCA$到根節(jié)點(diǎn)的路徑上都不會(huì)包括$w$這個(gè)權(quán)值。

我們從小到大枚舉權(quán)值，將這些路徑上用$w$覆蓋答案，覆蓋過(guò)的位置不再覆蓋，用一個(gè)并查集維護(hù)覆蓋過(guò)的集合即可，并查集的頭部指向集合中最頂部的節(jié)點(diǎn)即可。

時(shí)間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; const int N=1e6+10; struct node{int to,next; }a[N<<1]; int T,n,m,tot,ls[N],w[N],siz[N],f[N],v[N]; int fa[N],son[N],top[N],dep[N],ans[N]; int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } void print(int x) {if(x>9)print(x/10);putchar(x%10+'0');return;} void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs1(int x){dep[x]=dep[fa[x]]+1;siz[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[x])continue;fa[y]=x;dfs1(y);siz[x]+=siz[y];if(siz[y]>siz[son[x]])son[x]=y;}return; } void dfs2(int x){if(son[x]){top[son[x]]=top[x];dfs2(son[x]);}for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[x]||y==son[x])continue;top[y]=y;dfs2(y);}return; } int LCA(int x,int y){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=fa[top[x]];}return (dep[x]<dep[y])?x:y; } int find(int x) {return (f[x]==x)?x:(f[x]=find(f[x]));} int main() {freopen("game.in","r",stdin);freopen("game.out","w",stdout);scanf("%d",&T);while(T--){n=read();m=read();tot=v[0]=0;for(int i=1;i<=n;i++){w[i]=read();f[i]=i;ls[i]=v[i]=ans[i]=son[i]=fa[i]=0;}for(int i=1;i<n;i++){int x=read(),y=read();addl(x,y);addl(y,x);}top[1]=1;dfs1(1);dfs2(1);for(int i=1;i<=n;i++){if(w[i]>n)continue;if(!v[w[i]])v[w[i]]=i;else v[w[i]]=LCA(v[w[i]],i);}int p=0;for(;v[p];p++){int x=find(v[p]);while(x){ans[x]=p+1;f[x]=fa[x];x=find(x);}}for(int i=1;i<=n;i++)print(ans[i]?(ans[i]-1):p),putchar(' ');putchar('\n');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的jzoj5097-[GDOI2017day1]取石子游戏【并查集,LCA】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。