洛谷3703 SDOI2017树点涂色（LCT+线段树+dfs序）-白红宇

洛谷3703 SDOI2017树点涂色（LCT+线段树+dfs序）

阅读量：5282 次

发布时间：2019-06-14

本文共 3981 字，大约阅读时间需要 13 分钟。

又一道好题啊qwqqqq

一开始看这个题，还以为是一个树剖的什么毒瘤题目

（不过的确貌似可以用树剖啊）

qwq这真是一道$LCT$维护颜色的好题

首先，我们来一个一个操作的考虑。

对于操作$1$来说，我们是不是就相当于把$1~x$的路径，弄成一个独立的联通块？

哎，这个貌似是$access(x)$的操作理念啊QWQ

假设我们用$LCT$维护这棵树，一开始就全是虚边，然后对于一次1操作，那么就相当于一次$access$，那么权值的定义，也就相当于到1的路径上要经过多少个不同的$splay$（也就是轻边的数目+1）

起初每个点的权值，都是他的$deep$（我们假设根的$deep是1$），那么我们该如何询问一条路径上的权值和呢？

QWQ

由于我们的$LCT$，被当做来维护颜色了，所以自然不能通过$split$来算，因为会破坏原来的结构。

qwqqq

~~这时候就需要题解了~~

通常，我们求树上路径的方法一般都是树上差分。

那么这个题可以不可以用同样的方法来做呢？

我们来考虑证明一下（感性理解）

假设当前的两个点是$x,y$，他们的$LCA$记为$l$

先考虑存在同色的情况

$首先，我们可以知道，l只会和x，y其中一个同色。

显然$val[x]-val[l]$表示去掉LCA的这个点，$x`l$路径上的颜色个数，然后$val[y]-val[l]$同理。

而总的路径条数，显然等于两个式子相加，然后再加上$LCA$的颜色（因为$LCA$的颜色被减去了两次）。

正好就是我们树上差分的式子

\[val[x]+val[y]-2*val[LCA(x,y)] +1\]

。

那么我们现在就剩下最后一个问题了。

怎么维护修改和子树$max$呢？？

QWQ

既然没有修改，而且树的形态还是固定的。

那就可以直接线段树维护$dfs$序啊！

那么对于三操作就相当于子树求max

而对于子树的$val$的修改，我们可以发现，只有在每个$access$的时候，才会产生修改的影响（因为存在轻重边的切换），直接对应的+1,-1就行

但是有一个要注意的问题就是

！！！！我们修改的时候，要找到当前splay里面深度最小的点，把他和他的子树修改，这样才能起到整个子树都修改的效果

直接上代码

// luogu-judger-enable-o2#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #define mk makr_pair#define ll long longusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}const int maxn = 2e5+1e2;const int maxm = 2*maxn;int point[maxn],nxt[maxm],to[maxm];int cnt,n,m;int dfn[maxn],size[maxn],deep[maxn];int add[4*maxn],g[4*maxn];int f[maxn][21];int ch[maxn][3];int rev[maxn],fa[maxn];int back[maxn];int tot;void addedge(int x,int y){ nxt[++cnt]=point[x]; to[cnt]=y; point[x]=cnt;}void up(int root){ g[root]=max(g[2*root],g[2*root+1]); }void build(int root,int l,int r){ if (l==r) { g[root]=deep[back[l]]; return; } int mid = l+r >> 1; build(2*root,l,mid); build(2*root+1,mid+1,r); up(root);}void pushdown(int root,int l,int r){ if (add[root]) { add[root*2]+=add[root]; add[2*root+1]+=add[root]; g[2*root]+=add[root]; g[2*root+1]+=add[root]; add[root]=0; }}void update(int root,int l,int r,int x,int y,int p){ if (x>y) return; if (x<=l && r<=y) { g[root]+=p; add[root]+=p; return; } pushdown(root,l,r); int mid = l+r >> 1; if (x<=mid) update(2*root,l,mid,x,y,p); if (y>mid) update(2*root+1,mid+1,r,x,y,p); up(root);}int query(int root,int l,int r,int x,int y){ if (x>y) return 0; if (x<=l && r<=y) { return g[root]; } pushdown(root,l,r); int ans=0; int mid = l+r >> 1; if (x<=mid) ans=max(ans,query(2*root,l,mid,x,y)); if (y>mid) ans=max(ans,query(2*root+1,mid+1,r,x,y)); return ans;}void dfs(int x,int faa,int dep){ deep[x]=dep; dfn[x]=++tot; back[tot]=x; size[x]=1; for (int i=point[x];i;i=nxt[i]) { int p = to[i]; if (p==faa) continue; fa[p]=x; f[p][0]=x; dfs(p,x,dep+1); size[x]+=size[p]; }}void init(){ for (int j=1;j<=20;j++) for (int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];}int go_up(int x,int d){ for(int i=0;i<=20;i++) { if ((1<
            
             deep[y]) x=go_up(x,deep[x]-deep[y]); else y=go_up(y,deep[y]-deep[x]); 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 son(int x){ if (ch[fa[x]][0]==x) return 0; else return 1;}bool notroot(int x){ return ch[fa[x]][0]==x || ch[fa[x]][1]==x;}void rotate(int x){ int y=fa[x],z=fa[y]; int b=son(x),c=son(y); if (notroot(y)) ch[z][c]=x; fa[x]=z; ch[y][b]=ch[x][!b]; fa[ch[x][!b]]=y; ch[x][!b]=y; fa[y]=x;} void splay(int x){ while (notroot(x)) { int y = fa[x],z=fa[y]; int b=son(x),c=son(y); if(notroot(y)) { if (b==c) rotate(y); else rotate(x); } rotate(x); }}int findroot(int x){ while (ch[x][0]) x=ch[x][0]; return x;}void access(int x){ for (int y=0;x;y=x,x=fa[x]) { splay(x); int now = findroot(ch[x][1]); update(1,1,n,dfn[now],dfn[now]+size[now]-1,1); now=findroot(y); update(1,1,n,dfn[now],dfn[now]+size[now]-1,-1); ch[x][1]=y; }}int main(){ n=read(),m=read(); for (int i=1;i

转载于:https://www.cnblogs.com/yimmortal/p/10161935.html

你可能感兴趣的文章