二楼！
by Leap_Frog @ 2020-12-30 18:30:37
奇偶排序，块长 $\frac n{\sqrt m}$,TLE 70pts
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <cmath>
#define MAXN 100005
#define MAXM 5000005
using namespace std;
typedef long long ll;
inline int read()
{
int ans=0;
char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
char s[20],*tp=s;
inline void write(ll x)
{
if (!x) return (void)(puts("0"));
while (x) *(tp++)=x%10,x/=10;
while (tp>s) putchar(*(--tp)+'0');
puts("");
}
vector<int> e[MAXN];
int B;
struct query{int l,r,pos,sgn;}q[MAXM];
inline bool operator <(const query& a,const query& b){return (a.l/B==b.l/B)? ((a.l/B)&1)^(a.r<b.r):a.l<b.l;}
int a[MAXN],c[MAXN],val[MAXN],n,m,cnt;
int dfn[MAXN],dep[MAXN],fa[MAXN][20],lis[MAXN],ed[MAXN],tim,rt;
void dfs(int u,int f)
{
dep[lis[dfn[u]=++tim]=u]=dep[fa[u][0]=f]+1;
for (int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for (int i=0;i<(int)e[u].size();i++) if (e[u][i]!=f) dfs(e[u][i],u);
ed[u]=tim;
}
inline int findnxt(int x)
{
int y=rt;
for (int i=0;(1<<i)<dep[rt]-dep[x];i++)
if ((dep[rt]-dep[x]-1)&(1<<i))
y=fa[y][i];
return y;
}
inline bool isanc(int x,int y){return dfn[x]<=dfn[y]&&dfn[y]<=ed[x];}
int cntx[MAXN],cnty[MAXN],isq[MAXM];
ll res[MAXM],pre[MAXN];
inline ll solve(int x,int y,int T)
{
if (y==rt) swap(x,y);
if (x==rt)
{
if (y==rt) return pre[n];
if (isanc(y,rt))
{
y=findnxt(y);
return pre[n]-pre[ed[y]]+pre[dfn[y]-1];
}
else return pre[ed[y]]-pre[dfn[y]-1];
}
ll ans=0;
int s=1,tx=isanc(x,rt),ty=isanc(y,rt);
if (tx) x=findnxt(x);
if (ty) y=findnxt(y);
if (tx)
{
if (ty) ans+=pre[n]-pre[ed[y]]+pre[dfn[y]-1];
else ans+=pre[ed[y]]-pre[dfn[y]-1];
s=-s;
}
if (ty) ans+=s*(pre[ed[x]]-pre[dfn[x]-1]),s=-s;
q[++cnt]=(query){ed[x],ed[y],T,s};
q[++cnt]=(query){dfn[x]-1,ed[y],T,-s};
q[++cnt]=(query){ed[x],dfn[y]-1,T,-s};
q[++cnt]=(query){dfn[x]-1,dfn[y]-1,T,s};
return ans;
}
int main()
{
n=read(),m=read();
for (int i=1;i<=n;i++) val[++cnt]=c[i]=read();
sort(val+1,val+cnt+1);
cnt=unique(val+1,val+cnt+1)-val-1;
for (int i=1;i<=n;i++) c[i]=lower_bound(val+1,val+cnt+1,c[i])-val;
for (int i=1;i<n;i++)
{
int u,v;
u=read(),v=read();
e[u].push_back(v),e[v].push_back(u);
}
dfs(dep[1]=rt=1,cnt=0);
for (int i=1;i<=n;i++) ++cntx[a[i]=c[lis[i]]];
for (int i=1;i<=n;i++) pre[i]=pre[i-1]+cntx[a[i]];
for (int i=1;i<=n;i++) cntx[i]=0;
for (int T=1;T<=m;T++)
if (read()==1) rt=read();
else isq[T]=1,res[T]=solve(read(),read(),T);
for (int i=1;i<=cnt;i++) (q[i].l>q[i].r)&&(swap(q[i].l,q[i].r),0);
B=n/max(1,(int)sqrt(cnt));
sort(q+1,q+cnt+1);
int l=0,r=0;
ll ans=0;
cerr<<cnt;
for (int i=1;i<=cnt;i++)
{
while (r<q[i].r) ++cnty[a[++r]],ans+=cntx[a[r]];
while (l<q[i].l) ++cntx[a[++l]],ans+=cnty[a[l]];
while (r>q[i].r) ans-=cntx[a[r]],--cnty[a[r--]];
while (l>q[i].l) ans-=cnty[a[l]],--cntx[a[l--]];
res[q[i].pos]+=q[i].sgn*ans;
}
for (int i=1;i<=m;i++) (isq[i])&&(write(res[i]),0);
return 0;
}
```
不奇偶排序，块长 $\sqrt n$，AC，还跑得飞快
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <cmath>
#define MAXN 100005
#define MAXM 5000005
#define re register
using namespace std;
typedef long long ll;
inline int read()
{
int ans=0;
char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
char s[20],*tp=s;
inline void write(ll x)
{
if (!x) return (void)(puts("0"));
while (x) *(tp++)=x%10,x/=10;
while (tp>s) putchar(*(--tp)+'0');
puts("");
}
vector<int> e[MAXN];
int B;
struct query{int l,r,pos,sgn;}q[MAXM];
inline bool operator <(const query& a,const query& b)
{
if (a.l/B==b.l/B) return a.r<b.r;
return a.l<b.l;
}
int a[MAXN],c[MAXN],val[MAXN],n,m,cnt;
int dfn[MAXN],dep[MAXN],fa[MAXN][20],lis[MAXN],ed[MAXN],tim,rt;
void dfs(int u,int f)
{
dep[lis[dfn[u]=++tim]=u]=dep[fa[u][0]=f]+1;
for (int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for (int i=0;i<(int)e[u].size();i++) if (e[u][i]!=f) dfs(e[u][i],u);
ed[u]=tim;
}
inline int findnxt(int x)
{
int y=rt;
for (int i=0;(1<<i)<dep[rt]-dep[x];i++)
if ((dep[rt]-dep[x]-1)&(1<<i))
y=fa[y][i];
return y;
}
inline bool isanc(int x,int y){return dfn[x]<=dfn[y]&&dfn[y]<=ed[x];}
int cntx[MAXN],cnty[MAXN],isq[MAXM];
ll res[MAXM],pre[MAXN];
inline ll solve(int x,int y,int T)
{
if (y==rt) swap(x,y);
if (x==rt)
{
if (y==rt) return pre[n];
if (isanc(y,rt))
{
y=findnxt(y);
return pre[n]-pre[ed[y]]+pre[dfn[y]-1];
}
else return pre[ed[y]]-pre[dfn[y]-1];
}
ll ans=0;
int s=1,tx=isanc(x,rt),ty=isanc(y,rt);
if (tx) x=findnxt(x);
if (ty) y=findnxt(y);
if (tx)
{
if (ty) ans+=pre[n]-pre[ed[y]]+pre[dfn[y]-1];
else ans+=pre[ed[y]]-pre[dfn[y]-1];
s=-s;
}
if (ty) ans+=s*(pre[ed[x]]-pre[dfn[x]-1]),s=-s;
q[++cnt]=(query){ed[x],ed[y],T,s};
q[++cnt]=(query){dfn[x]-1,ed[y],T,-s};
q[++cnt]=(query){ed[x],dfn[y]-1,T,-s};
q[++cnt]=(query){dfn[x]-1,dfn[y]-1,T,s};
return ans;
}
int main()
{
n=read(),m=read();
for (int i=1;i<=n;i++) val[++cnt]=c[i]=read();
sort(val+1,val+cnt+1);
cnt=unique(val+1,val+cnt+1)-val-1;
for (int i=1;i<=n;i++) c[i]=lower_bound(val+1,val+cnt+1,c[i])-val;
for (int i=1;i<n;i++)
{
int u,v;
u=read(),v=read();
e[u].push_back(v),e[v].push_back(u);
}
dfs(dep[1]=rt=1,cnt=0);
for (int i=1;i<=n;i++) ++cntx[a[i]=c[lis[i]]];
for (int i=1;i<=n;i++) pre[i]=pre[i-1]+cntx[a[i]];
for (int i=1;i<=n;i++) cntx[i]=0;
for (int T=1;T<=m;T++)
if (read()==1) rt=read();
else isq[T]=1,res[T]=solve(read(),read(),T);
for (int i=1;i<=cnt;i++) (q[i].l>q[i].r)&&(swap(q[i].l,q[i].r),0);
B=sqrt(n);
cerr<<B<<'\n';
sort(q+1,q+cnt+1);
re int l=0,r=0;
re ll ans=0;
cerr<<cnt;
for (int i=1;i<=cnt;i++)
{
while (r<q[i].r) ++cnty[a[++r]],ans+=cntx[a[r]];
while (l<q[i].l) ++cntx[a[++l]],ans+=cnty[a[l]];
while (r>q[i].r) ans-=cntx[a[r]],--cnty[a[r--]];
while (l>q[i].l) ans-=cnty[a[l]],--cntx[a[l--]];
res[q[i].pos]+=q[i].sgn*ans;
}
for (int i=1;i<=m;i++) (isq[i])&&(write(res[i]),0);
return 0;
}
```
by Lstdo @ 2020-12-30 18:31:54
@[Lstdo](/user/53930)
可能这道题拆出来的询问有一些奇奇怪怪的性质？
而且理论是理论，实际是实际，不能一概而论
by DPair @ 2020-12-30 18:35:10
我目前只想到这一种玄学解释。
by DPair @ 2020-12-30 18:35:28
@[Lstdo](/user/53930) 都说了那是理论，而根据数据的不同效率肯定是不同的，你还可以把块长调成 $200$ 试一下。不过奇偶优化应该是有用的啊/yun
by Gemini7X @ 2020-12-30 18:37:15
@[Lstdo](/user/53930) 你看，[块长200+奇偶优化](https://www.luogu.com.cn/record/44430387)跑得比你还快呢。
by Gemini7X @ 2020-12-30 18:40:18
@[Lstdo](/user/53930) 而且我还没开O2
by Gemini7X @ 2020-12-30 18:40:50
好像奇偶排序是排序的cmp常数太大了(?)
好玄学啊
by Lstdo @ 2020-12-30 18:41:00
精确调块长 ×
玄学调块长 √
by Gemini7X @ 2020-12-30 18:43:53
@[Lstdo](/user/53930) 有个鬼的常数，一个 $nlog{n}$ 的地方你告诉我常数很大？
by Gemini7X @ 2020-12-30 18:44:47