首先，乖♂乖♂交♂出数据生成器：

#include <bits/stdc++.h>
using namespace std;
inline int gen(){
    return (rand()<<15)|(rand());
}
int main(){
    srand(time(NULL));
    int n=1000,m=1000;
    printf("%d %d\n",n,m);
    for (register int i=1;i<=n;++i){
        printf("%d ",gen()%10+1);
    }
    printf("\n");
    for (register int i=2;i<=n;++i){
        printf("%d %d\n",i,gen()%(i-1)+1);
    }
    printf("\n");
    for (register int i=1;i<=m;++i){
        int opr=(rand()%10==0)?1:2;
        printf("%d %d\n",opr,gen()%n+1);
    }
}

使用printf("%d ",gen()%10+1);是因为如果 $val[i]$ 的范围太大，数据基本上全是 $0$ 。

所以这题的数据范围是假的，当然最后一个点是真·数据范围。

为什么int opr=(rand()%10==0)?1:2;呢？，是因为换♂根太多也不好啊。

$30pts$

真·大暴力，每次求出颜色总数，根据组合数算一下就可以了：

#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
int col[MAXN];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int nowu;
int val[MAXN];
void dfs(int u,int father,bool in){
    if (u==nowu) in=true;
    if (in) col[val[u]]++;
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=father){
            dfs(v,u,in);
        }
    }
}
int main(){
    int n=read(),m=read();
    for (register int i=1;i<=n;++i) val[i]=read();
    for (register int i=1;i<n;++i){
        int u=read(),v=read();
        AddEdge(u,v);
        AddEdge(v,u);
    }
    int rt=1;
    for (register int i=1;i<=m;++i){
        int opr=read();
        if (opr==1) rt=read();
        else {
            nowu=read();
            memset(col,0,sizeof(col));
            dfs(rt,rt,0);
            int ans=0;
            for (register int i=1;i<=n;++i){
                if (col[i]>1) ans+=col[i]*(col[i]-1)/2;
            }
            printf("%d\n",ans);
        }
    }
}

100pts

考虑莫队，首先，参考这篇题解，你就会发现这个换根是假的。

前两种情况，就是查询 $[1,n]$ 和 $[L[u],R[u]]$ 直接放进一个莫队里面搞就可以了，但是别忘了还要查询 $[1,L[v]-1]$ ， $[R[v]+1,n]$ ，如果 $i$ ， $j$ 都在 $[1,L[v]-1]$ ，或者都在 $[R[v]+1,n]$ 还是可以套用上面的方法，如果 $i$ 在 $[1,L[v]-1]$ ， $j$ 在 $[R[v]+1,n]$ 的话，怎么搞呢？

我想了一个笨办法，再开一个莫队就可以了，询问 $i \in[1,l],j \in [r,n]$ 之间数对的个数，最后加起来就可以了。

if (u==rt){
     AddQuery1(1,n,qu);
}
else if (LCA(u,rt)==u){
    int v=Hop(rt,u);
    if (L[v]>1) AddQuery1(1,L[v]-1,qu);
    if (R[v]<n) AddQuery1(R[v]+1,n,qu);
    AddQuery2(L[v]-1,R[v]+1,qu);
}
else {
    AddQuery1(L[u],R[u],qu);
}

献上写得很丑的标算，注意要开 $\text{long long}$ ，我应该刻意卡了 $\text {int}$ ：

时间复杂度 $O(n \sqrt n)$

#include <bits/stdc++.h>
#define MAXN 500005
#define MAXM 19
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int L[MAXN],R[MAXN],dfn,seq[MAXN];
int anc[MAXN][MAXM],dep[MAXN];
int val[MAXN],n,m;
void dfs(int u,int father){
    seq[L[u]=++dfn]=val[u];
    anc[u][0]=father;
    for (register int i=1;i<MAXM;++i) anc[u][i]=anc[anc[u][i-1]][i-1];
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=father){
            dep[v]=dep[u]+1;
            dfs(v,u);
        }
    }
    R[u]=dfn;
}
inline int LCA(int u,int v){
    if (dep[u]<dep[v]) swap(u,v);
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>=dep[v]) u=anc[u][i];
    }
    if (u==v) return u;
    for (register int i=MAXM-1;i>=0;--i){
        if (anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i];
    }
    return anc[u][0];
}
inline int Hop(int u,int v){//h♂p to v's son
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>dep[v]){
            u=anc[u][i];
        }
    }
    return u;
}
int pos[MAXN],rt;
struct Query1{
    int l,r;//表示询问[l,r]内相同的数对个数
    int id;
}q1[MAXN];
inline bool operator < (const Query1 &a,const Query1 &b){
    return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
struct Query2{
    int l,r;//表示询问[1,l][r,n]之间相同数对的个数
    int id;
}q2[MAXN];
inline bool operator < (const Query2 &a,const Query2 &b){
    return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
int c1,c2;
inline void AddQuery1(int l,int r,int id){q1[++c1]=Query1{l,r,id};}
inline void AddQuery2(int l,int r,int id){q2[++c2]=Query2{l,r,id};}
int cnt[MAXN];
int cnt1[MAXN],cnt2[MAXN];
long long Ans[MAXN],ans;
inline void Add(int x){
    ++cnt[x],ans+=(cnt[x]-1);//除去自己
}
inline void Del(int x){
    ans-=(cnt[x]-1),--cnt[x];
}
#undef int
int main(){
#define int long long
    n=read(),m=read();
    for (register int i=1;i<=n;++i){
        val[i]=read();
    }

    int Size=sqrt(n);
    for (register int i=1;i<=n;++i){
        pos[i]=(i-1)/Size+1;
    }

    for (register int i=1;i<n;++i){
        int u=read(),v=read();
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs(1,1);
	 
    rt=1;
    int qu=0;
    for (register int i=1;i<=m;++i){
        int opr=read();
        if (opr==1){
            rt=read();
        }
        else {
            qu++;
            int u=read();
            if (u==rt){
                AddQuery1(1,n,qu);
            }
            else if (LCA(u,rt)==u){
                int v=Hop(rt,u);
                if (L[v]>1) AddQuery1(1,L[v]-1,qu);
                if (R[v]<n) AddQuery1(R[v]+1,n,qu);
                AddQuery2(L[v]-1,R[v]+1,qu);
            }
            else {
                AddQuery1(L[u],R[u],qu);
            }
        }
    }
    //to compelete Query1
    sort(q1+1,q1+1+c1);
    int l=1,r=0;
    ans=0;
    for (register int i=1;i<=c1;++i){
        while (l<q1[i].l) Del(seq[l++]);
        while (l>q1[i].l) Add(seq[--l]);
        while (r<q1[i].r) Add(seq[++r]);
        while (r>q1[i].r) Del(seq[r--]);
        Ans[q1[i].id]+=ans;
    }

    //to compelete Query2
    sort(q2+1,q2+1+c2);
    l=0,r=n+1;
    ans=0;
    for (register int i=1;i<=c2;++i){
        while (l<q2[i].l){
            ++cnt1[seq[++l]];
            ans+=cnt2[seq[l]];
        }
        while (l>q2[i].l){
            --cnt1[seq[l]];
            ans-=cnt2[seq[l--]];
        }
        while (r<q2[i].r){
            --cnt2[seq[r]];
            ans-=cnt1[seq[r++]];
        }
        while (r>q2[i].r){
            ++cnt2[seq[--r]];
            ans+=cnt1[seq[r]];
        }
        Ans[q2[i].id]+=ans;
    }
    for (register int i=1;i<=qu;++i){
        printf("%lld\n",Ans[i]);
    }
}

这道题 $O(n \log n)$ 预处理 $O(1)$ 查询的方法应该也有，但是我太菜了，不想写。

你们写出来就可以爆碾标算了。

Steven_Meng's Blog

U81395 换根の树

$30pts$

100pts

最后一个点出锅了，正在修复

下一篇：BZOJ3262 陌上花开

Steven_Meng's Blog

U81395 换根の树

30pts30pts30pts

100pts

最后一个点出锅了，正在修复

下一篇：BZOJ3262 陌上花开

$30pts$