正題

題目鏈接:https://www.luogu.com.cn/problem/P3703

---

題目大意

$n$個點的一棵樹開始所有點有不同的顏色，$m$次操作

將根節點到$x$節點的路徑上染上一種新的顏色

詢問一條路徑的不同顏色個數

詢問一個節點的子樹中的一個$x$使得$x$到根節點的顏色最多。

---

解題思路

操作$1$和$LCT$的$access$操作很相似。相同顏色之間就是實邊，不同顏色之間就是虛邊。

操作$2$就是之間$p_x+p_y?2p_{LCA}+1$就好了，但是考慮到操作$3$，所以維護一個$dfn$序和線段樹就可以查詢子樹最大值了。

之后維護一個$LCT$，在$access$操作切換虛實邊的時候修改一下線段樹就好了，并且需要注意我們不能直接拿$Splay$的根的子樹，要找到實際的樹中的根，所以$Splay$一直往左就好了。

好像還有樹鏈剖分的做法，線段樹查詢的時候維護一下末尾顏色好像就可以了，這里不多講（我也不會）

時間復雜度$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; struct node{int to,next; }a[N<<1]; int n,m,cnt,tot,ls[N],rfn[N],ed[N],fa[N]; int dep[N],son[N],siz[N],top[N]; struct SegTree{int w[N<<2],lazy[N<<2];void Downdata(int x){if(!lazy[x])return;w[x*2]+=lazy[x];lazy[x*2]+=lazy[x];w[x*2+1]+=lazy[x];lazy[x*2+1]+=lazy[x];lazy[x]=0;return;}void Change(int x,int L,int R,int l,int r,int val){if(L==l&&R==r){w[x]+=val;lazy[x]+=val;return;}int mid=(L+R)>>1;Downdata(x);if(r<=mid)Change(x*2,L,mid,l,r,val);else if(l>mid)Change(x*2+1,mid+1,R,l,r,val);else Change(x*2,L,mid,l,mid,val),Change(x*2+1,mid+1,R,mid+1,r,val);w[x]=max(w[x*2],w[x*2+1]);return;}int Ask(int x,int L,int R,int l,int r){if(L==l&&R==r)return w[x];int mid=(L+R)>>1;Downdata(x);if(r<=mid)return Ask(x*2,L,mid,l,r);if(l>mid)return Ask(x*2+1,mid+1,R,l,r);return max(Ask(x*2,L,mid,l,mid),Ask(x*2+1,mid+1,R,mid+1,r));} }Tr; struct LinkCutTree{int t[N][2],fa[N];bool Nroot(int x){return fa[x]&&(t[fa[x]][0]==x||t[fa[x]][1]==x);}bool Direct(int x){return t[fa[x]][1]==x;}void Rotate(int x){int y=fa[x],z=fa[y];int xs=Direct(x),ys=Direct(y);int w=t[x][xs^1];if(Nroot(y))t[z][ys]=x;t[x][xs^1]=y;t[y][xs]=w;if(w)fa[w]=y;fa[y]=x;fa[x]=z;return;}void Splay(int x){while(Nroot(x)){int y=fa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)==Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}int FindRoot(int x){while(t[x][0])x=t[x][0];return x;}void Access(int x){for(int y=0;x;y=x,x=fa[x]){Splay(x);int z=t[x][1];if(z)z=FindRoot(z),Tr.Change(1,1,n,rfn[z],ed[z],1);if(y)z=FindRoot(y),Tr.Change(1,1,n,rfn[z],ed[z],-1);t[x][1]=y;}return;} }T; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs1(int x){siz[x]=1;rfn[x]=++cnt;dep[x]=dep[fa[x]]+1;T.fa[x]=fa[x];Tr.Change(1,1,n,cnt,cnt,dep[x]);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;}ed[x]=cnt; } 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 main() {// freopen("paint1.in","r",stdin);scanf("%d%d",&n,&m);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}dfs1(1);dfs2(1);while(m--){int op,x,y;scanf("%d%d",&op,&x);if(op==1)T.Access(x);else if(op==2){scanf("%d",&y);int lca=LCA(x,y);int p1=Tr.Ask(1,1,n,rfn[x],rfn[x]);int p2=Tr.Ask(1,1,n,rfn[y],rfn[y]);int p3=Tr.Ask(1,1,n,rfn[lca],rfn[lca]);printf("%d\n",p1+p2-p3*2+1);}else printf("%d\n",Tr.Ask(1,1,n,rfn[x],ed[x]));}return 0; }

總結

以上是生活随笔為你收集整理的P3703-[SDOI2017]树点涂色【LCT,线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。