洛谷P4689 [Ynoi2016]这是我自己的发明（树上莫队+树链剖分）

àì夳堔傛蜴生んèń 2022-01-12 09:49 171阅读 0赞

## 题目描述 ##

您正在打galgame，然后突然家长进来了，于是您假装在写数据结构题：

给一个树，n 个点，有点权，初始根是 1。

m 个操作，每次操作：

1.将树根换为 x。

2.给出两个点 x，y，从 x 的子树中选每一个点，y 的子树中选每一个点，如果两个点点权相等，ans++，求 ans。

**题解**

**　　**lxl的大毒瘤题名不虚传

顺便先膜一下gxz大佬再说（毕竟像我这种菜鸡根本想不出这么巧的方法）->[这里][Link 1]

首先，如果没有换根的话，那么可以直接把子树当成dfs序上的一段区间来做，那么只要把询问给拆成好几个询问，然后直接用莫队就可以了

然后考虑换根要怎么解决呢？可以参考[【bzoj3083】遥远的国度][bzoj3083]，把子树变成原来的dfs序中的最多两段区间

然后考虑块的大小，大佬说这题卡常，得把块的大小调成$\\frac\{n\}\{\\sqrt\{m\}\}\*2$，否则会被卡，然而亲测不用乘2也能过……虽然跑得稍微慢了点

顺带提一句，这里的莫队范围是$(1,x)$而不是$(l,r)$（因为是把询问写成了前缀和相减的形式），当初刚看到的时候没看懂还写错了……

1 //minamoto
      2 #include<iostream>
      3 #include<cstdio>
      4 #include<cmath>
      5 #include<algorithm>
      6 #define ll long long
      7 using namespace std;
      8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
      9 char buf[1<<21],*p1=buf,*p2=buf;
     10 inline int read(){
     11     #define num ch-'0'
     12     char ch;bool flag=0;int res;
     13     while(!isdigit(ch=getc()))
     14     (ch=='-')&&(flag=true);
     15     for(res=num;isdigit(ch=getc());res=res*10+num);
     16     (flag)&&(res=-res);
     17     #undef num
     18     return res;
     19 }
     20 char sr[1<<21],z[20];int C=-1,Z;
     21 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
     22 inline void print(ll x){
     23     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
     24     while(z[++Z]=x%10+48,x/=10);
     25     while(sr[++C]=z[Z],--Z);sr[++C]='\n';
     26 }
     27 const int N=100005;
     28 int a[N],b[N],head[N],Next[N<<1],ver[N<<1],tot;
     29 int dep[N],ls[N],rs[N],son[N],sz[N],top[N],fa[N],cnt;
     30 int vx[5],ox[5],tx,vy[5],oy[5],ty,cx[N],cy[N],w[N],px,py;
     31 ll ans[N*5],now;
     32 int n,m,rt,cq,num=0;
     33 struct node{
     34     int l,r,rt,id,opt;
     35     node(){}
     36     node(int L,int R,int Id,int Opt){l=min(L,R),r=max(L,R),id=Id,opt=Opt;}
     37     bool operator<(const node &a)const {
        return rt == a.rt ? r < a.r : l < a.l;}
     38     //inline bool operator <(const node &b)const{return rt==b.rt?rt&1?r<b.r:r>b.r:rt<b.rt;}
     39 }q[N*45];
     40 inline void add(int u,int v){
     41     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
     42     ver[++tot]=u,Next[tot]=head[v],head[v]=tot;
     43 }
     44 void dfs1(int u){
     45     sz[u]=1,dep[u]=dep[fa[u]]+1;
     46     for(int i=head[u];i;i=Next[i]){
     47         int v=ver[i];
     48         if(v!=fa[u]){
     49             fa[v]=u,dfs1(v),sz[u]+=sz[v];
     50             if(sz[v]>sz[son[u]]) son[u]=v;
     51         }
     52     }
     53 }
     54 void dfs2(int u,int t){
     55     top[u]=t,ls[u]=++cnt,w[cnt]=a[u];
     56     if(son[u]){
     57         dfs2(son[u],t);
     58         for(int i=head[u];i;i=Next[i]){
     59             int v=ver[i];
     60             if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
     61         }
     62     }
     63     rs[u]=cnt;
     64 }
     65 inline int find(int t,int u){
     66     while(top[u]!=top[t]){
     67         if(fa[top[u]]==t) return top[u];
     68         u=fa[top[u]];
     69     }
     70     return son[t];
     71 }
     72 int main(){
     73     //freopen("testdata.in","r",stdin);
     74     n=read(),m=read();
     75     for(int i=1;i<=n;++i) a[i]=b[i]=read();
     76     sort(b+1,b+1+n);
     77     for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
     78     for(int i=1;i<n;++i){
     79         int u=read(),v=read();add(u,v);
     80     }
     81     dfs1(1),dfs2(1,1);
     82     for(int i=1;i<=m;++i){
     83         int op=read(),x=read(),y,z;
     84         if(op&1) rt=x;
     85         else{
     86             y=read(),++cq;
     87             tx=ty=0;
     88             if(x==rt) vx[++tx]=n,ox[tx]=1;
     89             else if(ls[rt]<ls[x]||ls[rt]>rs[x]) vx[++tx]=rs[x],ox[tx]=1,vx[++tx]=ls[x]-1,ox[tx]=-1;
     90             else z=find(x,rt),vx[++tx]=n,ox[tx]=1,vx[++tx]=rs[z],ox[tx]=-1,vx[++tx]=ls[z]-1,ox[tx]=1;
     91             if(y==rt) vy[++ty]=n,oy[ty]=1;
     92             else if(ls[rt]<ls[y]||ls[rt]>rs[y]) vy[++ty]=rs[y],oy[ty]=1,vy[++ty]=ls[y]-1,oy[ty]=-1;
     93             else z=find(y,rt),vy[++ty]=n,oy[ty]=1,vy[++ty]=rs[z],oy[ty]=-1,vy[++ty]=ls[z]-1,oy[ty]=1;
     94             for(int j=1;j<=tx;++j)
     95             for(int k=1;k<=ty;++k)
     96             if(vx[j]&&vy[k])
     97             q[++num]=node(vx[j],vy[k],cq,ox[j]*oy[k]);
     98 }
     99     }
    100     int s=(n/sqrt(num))*2+1;
    101     for(int i=1;i<=num;++i) q[i].rt=(q[i].l-1)/s;
    102     sort(q+1,q+1+num);
    103     for(int i=1;i<=num;++i){
    104         while(px<q[i].l) now+=cy[w[++px]],++cx[w[px]];
    105         while(py<q[i].r) now+=cx[w[++py]],++cy[w[py]];
    106         while(px>q[i].l) --cx[w[px]],now-=cy[w[px--]];
    107         while(py>q[i].r) --cy[w[py]],now-=cx[w[py--]];
    108         ans[q[i].id]+=now*q[i].opt;
    109     }
    110     for(int i=1;i<=cq;++i) print(ans[i]);
    111     Ot();
    112     return 0;
    113 }

转载于:https://www.cnblogs.com/bztMinamoto/p/9559510.html

[Link 1]: https://www.cnblogs.com/GXZlegend/p/7598214.html
[bzoj3083]: https://www.cnblogs.com/bztMinamoto/p/9557244.html