[Ynoi2016]这是我自己的发明

第一道Ynoi，blog总要有个Ynoi题解来装x。

传送门

一句话题意：求区间相同颜色的数对数，上树做，要求支持换根。

在做这题之前我见过[Snoi2017]一个简单的询问，所以如果这是一个序列上的问题的话：

$f(l1,r1,l2,r2)$表示询问l1,r1,l2,r2的答案，显然四个关键字不能莫队，但是我们可以容斥。
$$
f(l1,r1,l2,r2)=f(1,r1,1,r2)-f(1,l1-1,l2,r2)-f(l1,r1,l2-1,r2)+f(1,l1-1,1,l2-1)
$$
很多问你两个区间满足什么条件的数对数都可以容斥成这样，比如[HAOI2011 Problem b]。

这样一个询问就只有两个关键字了。

在树上的做法：

因为有换根的操作，所以可能会是一个区间对多个区间甚至多个区间对多个区间。

例如：三个区间[l1,r1],[l2,r2],[l3,r3]和三个个区间[l1‘,r1’],[l2’,r2’],[l3’,r3’]中的答案数。

把两边区间每一对都对应即可，就是3*3=9个询问。

换根的话分类讨论，如果新根不在x的子树内相安无事，否则x子树的区间就是除了x向新根那个方向的儿子的子树，以外的所有点，dfs序搞一搞就好了。

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#ifdef ONLINE_JUDGE
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void read(T&x){
    static char c;static int y;
    for(c=gc(),x=0,y=1;c<48||57<c;c=gc())if(c=='-')y=-1;
    for(;48<=c&&c<=57;c=gc())x=((x+(x<<2))<<1)+(c^'0');
    x*=y;
}
#else
void read(int&x){scanf("%d",&x);}
#endif
struct node{
    int next,to;
}w[400001];
struct ques{
    int h,l,r,f;
}q[8000011];
struct ls{
    int h,z;
}a[100001];
int rt,now,num,hs[100001],head[100001],idx[100001],size[100001];
int r,lx[201],n,b[100001],dfn[100001],fa[100001],bl[100001],cnt;
int m,l,ly[201],o[100001][2],que,fx[201],fy[201],blo,top[100001];
ll ans[500001],sum;
inline bool cmp2(ls c,ls d){return c.z<d.z;}
inline bool cmp(ques c,ques d){
    if (bl[c.l]!=bl[d.l]) return c.l<d.l;
    if (bl[c.l]&1) return c.r<d.r;
    else return c.r>d.r;
    // return (c.r<d.r)^(bl[c.l]&1)^1;
}
inline void add_edge(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; head[x]=cnt;
}
void dfs1(int x,int da){
    dfn[++num]=b[x]; idx[x]=num; size[x]=1;
    for (int i=head[x]; i; i=w[i].next){
        if (w[i].to!=da){
            fa[w[i].to]=x;
            dfs1(w[i].to,x);
            size[x]+=size[w[i].to];
            if (size[w[i].to]>size[hs[x]]) hs[x]=w[i].to;
        }
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    if (hs[x]) dfs2(hs[x],tp);
    // top[x]=x;
    for (int i=head[x]; i; i=w[i].next)
        if (w[i].to!=hs[x]&&w[i].to!=fa[x])
            dfs2(w[i].to,w[i].to);
}
inline int find(int y,int x){
    int u;
    while (top[x]!=top[y]) u=top[x],x=fa[u];
    if (x==y) return u; return hs[y];
}
inline void build(int x,int y){
    int nx=0,ny=0;
    int l1=idx[x],r1=idx[x]+size[x]-1;
    int l2=idx[y],r2=idx[y]+size[y]-1;
    if (x==rt) lx[++nx]=n,fx[nx]=1;
    else
        if (idx[x]<=idx[rt]&&idx[rt]<=idx[x]+size[x]-1){
            int z=find(x,rt);
            lx[++nx]=idx[z]-1; fx[nx]=1;
            lx[++nx]=idx[z]+size[z]-1; fx[nx]=-1;
            lx[++nx]=n; fx[nx]=1;
        }
        else{
            lx[++nx]=r1; fx[nx]=1;
            lx[++nx]=l1-1; fx[nx]=-1;
        }
    if (y==rt) ly[++ny]=n,fy[ny]=1;
    else
        if (idx[y]<=idx[rt]&&idx[rt]<=idx[y]+size[y]-1){
            int z=find(y,rt);
            ly[++ny]=idx[z]-1; fy[ny]=1;
            ly[++ny]=idx[z]+size[z]-1; fy[ny]=-1;
            ly[++ny]=n; fy[ny]=1;
        }
        else{
            ly[++ny]=r2; fy[ny]=1;
            ly[++ny]=l2-1; fy[ny]=-1;
        }
    for (int i=1; i<=nx; i++)
        for (int j=1; j<=ny; j++)
            if (lx[i]&&ly[j])
                q[++que].h=now,q[que].l=lx[i],q[que].r=ly[j],q[que].f=fx[i]*fy[j];
}
inline void add(int x,int y){o[dfn[x]][y]++; sum+=o[dfn[x]][y^1];}
inline void del(int x,int y){o[dfn[x]][y]--; sum-=o[dfn[x]][y^1];}
int main(){
    int x,y,opt;
    read(n),read(m);
    for (int i=1; i<=n; i++) read(a[i].z),a[i].h=i;
    sort(a+1,a+n+1,cmp2);
    for (int i=1; i<=n; i++){
        b[a[i].h]=b[a[i-1].h]; if (a[i].z!=a[i-1].z) b[a[i].h]++;
    }

    // puts("dllxl");
    for (int i=1; i<n; i++){
        read(x),read(y);
        add_edge(x,y); add_edge(y,x);
    }
    dfs1(1,0); dfs2(1,1); rt=1;
    for (int i=1; i<=m; i++){
        read(opt);
        if (opt==1) read(rt);
        else{
            read(x),read(y);
            now++; build(x,y);
        }
    }
    blo=sqrt(n);
    for (int i=1; i<=n; i++) bl[i]=(i-1)/blo+1;
    sort(q+1,q+que+1,cmp);//	return 0;
    for (int i=1; i<=que; i++){
        while (l<q[i].l) l++,add(l,0);
        while (l>q[i].l) del(l,0),l--;
        while (r<q[i].r) r++,add(r,1);
        while (r>q[i].r) del(r,1),r--;
        ans[q[i].h]+=sum*q[i].f;
    }
    for (int i=1; i<=now; i++) printf("%lld\n",ans[i]);
    return 0;
}