Description
Link.
给一个树，$n$ 个点，有点权，初始根是 1。
$m$ 个操作，种类如下：
1 x 将树根换为 $x$。
2 x y 给出两个点 $x,y$，从 $x$ 的子树中选每一个点，$y$ 的子树中选每一个点，求点权相等的情况数。
Solution
我首先认为这是 SNOI2017 一个简单的询问 搬到树上。
我们传统地把此题分为两个 $\texttt{pass}$，一个询问，一个修改。
- $\texttt{pass 1}$：询问
我直接按 一个简单的询问 的方法讲。其实是把以前的题解 copy 过来了。
由于是出现次数，满足区间加减性，所以我们可以这样表达 $\mathrm{get}(l,r,x)$（省略 $x$）:
$$ \mathrm{get}(l,r)=\mathrm{get}(1,r)-\mathrm{get}(1,l-1) $$
那么我们代进原式，化一波式子（$\mathrm{get}(p)=\mathrm{get}(1,p,x)$）：
$$ \sum_{i=1}^{\infty}\mathrm{get}(l_{1},r_{1},x)\times\mathrm{get}(l_{2},r_{2},x) $$
$$ \sum_{i=1}^{\infty}(\mathrm{get}(1,r_{1})-\mathrm{get}(1,l_{1}-1))\times(\mathrm{get}(1,r_{2})-\mathrm{get}(1,l_{2}-1)) $$
$$ \sum_{i=1}^{\infty}\mathrm{get}(r_{1})\times\mathrm{get}(r_{2})-\mathrm{get}(r_{1})\times\mathrm{get}(l_{2}-1)-\mathrm{get}(l_{1}-1)\times\mathrm{get}(r_{2})+\mathrm{get}(l_{1}-1))\times\mathrm{get}(l_{2}-1) $$
$$ \mathrm{let}\ F(x,y)=\sum_{d}\mathrm{get}(1,l,d)\times\mathrm{get}(1,r,d) $$
则答案为:
$$ F(r_{1},r_{2})-F(r_{1},l_{2}-1)-F(l_{1}-1,r_{2})+F(l_{1}-1,l_{2}-1) $$
考虑怎么更新，比如从 $l$ 更新到 $l+1$，则：
$$ \mathrm{get(1,l)}\times\mathrm{get}(1,r) $$
$$ \mathrm{get(1,l+1)}\times\mathrm{get}(1,r) $$
$$ \mathrm{get(1,l)}\times\mathrm{get}(1,r)+\mathrm{cont}(a_{l}) $$
其中 $\mathrm{cont}(a_{l})$ 表示 $a_{l}$ 的出现次数。
则我们就知道怎么更新了，由于我们维护和的是前缀信息，所以姿势和普通莫队有点不一样。
维护两个数组 cntl[x] 和 cntr[y] 表示答案式子
$$ F(r_{1},r_{2})-F(r_{1},l_{2}-1)-F(l_{1}-1,r_{2})+F(l_{1}-1,l_{2}-1) $$
子树的话直接 DFS 序拍到序列上。
- $\texttt{pass 2}$：修改
现在我们面临着查询操作我们是用莫队整的，但这个修改貌似不单纯。其实也是从树剖模板缝合过来的。
分类讨论，设我们当前要换的根为 $rt$，现在来处理询问，设查询的节点为 $u$，$\text{LCA}(u,v)$ 为节点 $u$ 和节点 $v$ 的最近公共祖先。
- 如果 $rt=u$，则我们直接对整棵树进行查询。
- 如果 $\text{LCA}(u,rt)\neq u$，此时修改不影响查询。
- 如果 $\text{LCA}(u,rt)=u$，此时 $rt$ 在 $u$ 的子树里，那么需要查询的地方就很明确了，后面的步骤显然。
于是我们不需要实际的去处理这个修改，然后就可以直接莫队了。
（整体感觉是个 原题+假上树+树剖模板 的缝合题）
/* Clearink */
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 5e5 + 5, MAXM = 1e6 + 5;
int rint () {
int x = 0, f = 1; char c = getchar ();
for ( ; c < '0' || c > '9'; c = getchar () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = getchar () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<class _T>
void wint ( _T x ) {
if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
if ( x > 9 ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
template<class _T> void swapp ( _T& x, _T& y ) { _T w = x; x = y; y = w; }
struct GraphSet {
int to, nx;
GraphSet () : to ( 0 ), nx ( 0 ) {}
GraphSet ( const int a, const int b ) : to ( a ), nx ( b ) {}
} asg[MAXN * 2];
struct Quest {
int l, r, ID, x;
Quest () : l ( 0 ), r ( 0 ), ID ( 0 ), x ( 0 ) {}
Quest ( const int a, const int b, const int c, const int d ) : l ( a ), r ( b ), ID ( c ), x ( d ) {}
} asq[MAXM * 8], itls[MAXN];
LL cur = 0, ans[MAXM], buc1[MAXN], buc2[MAXN];
int rt, pos[MAXN], blo = 320, col[MAXN], freq;
int n, m, bgn[MAXN], cnt, sjc, segl[MAXN], segr[MAXN], kfa[MAXN][21], a[MAXN], dept[MAXN], pri[MAXN], len;
void addE ( const int u, const int v ) { asg[++ cnt] = GraphSet ( v, bgn[u] ), bgn[u] = cnt; }
bool existcmp ( const Quest& one, const Quest& ano ) { return pos[one.l] == pos[ano.l] ? one.r < ano.r : one.l < ano.l; }
void dfs ( const int u, const int lst ) {
kfa[u][0] = lst, dept[u] = dept[lst] + 1;
segl[u] = ++ sjc, col[sjc] = a[u];
for ( int i = 1; i <= 20; ++ i ) kfa[u][i] = kfa[kfa[u][i - 1]][i - 1];
for ( int i = bgn[u]; i; i = asg[i].nx ) {
int v = asg[i].to;
if ( v == lst ) continue;
dfs ( v, u );
}
segr[u] = sjc;
}
int calcKAC ( int u, int k ) {
for ( int i = 20; ~ i; -- i ) {
if ( k >= ( 1 << i ) ) k -= ( 1 << i ), u = kfa[u][i];
}
return u;
}
int calcLCA ( int u, int v ) {
if ( dept[u] < dept[v] ) swapp ( u, v );
for ( int i = 20; ~ i; -- i ) {
if ( dept[kfa[u][i]] >= dept[v] ) u = kfa[u][i];
}
if ( u == v ) return u;
for ( int i = 20; ~ i; -- i ) {
if ( kfa[u][i] != kfa[v][i] ) u = kfa[u][i], v = kfa[v][i];
}
return kfa[u][0];
}
void initial () {
for ( int i = 1; i <= n; ++ i ) pos[i] = ( i - 1 ) / blo + 1;
sort ( pri + 1, pri + 1 + n );
len = unique ( pri + 1, pri + 1 + n ) - pri - 1;
for ( int i = 1; i <= n; ++ i ) a[i] = lower_bound ( pri + 1, pri + 1 + len, a[i] ) - pri;
dfs ( 1, 0 );
}
void splitASdrug ( const int u, int& ils ) {
if ( u == rt ) itls[++ ils] = Quest ( 1, n, 0, 0 );
else {
int lca = calcLCA ( u, rt );
if ( lca != u ) itls[++ ils] = Quest ( segl[u], segr[u], 0, 0 );
else {
int ar = calcKAC ( rt, dept[rt] - dept[u] - 1 );
if ( 1 <= segl[ar] - 1 ) itls[++ ils] = Quest ( 1, segl[ar] - 1, 0, 0 );
if ( segr[ar] + 1 <= n ) itls[++ ils] = Quest ( segr[ar] + 1, n, 0, 0 );
}
}
}
void transASsub ( const int l1, const int r1, const int l2, const int r2, const int ID ) {
asq[++ m] = Quest ( r1, r2, ID, 1 ), asq[++ m] = Quest ( r1, l2 - 1, ID, -1 );
asq[++ m] = Quest ( l1 - 1, r2, ID, -1 ), asq[++ m] = Quest ( l1 - 1, l2 - 1, ID, 1 );
}
void transASmany ( const int l, const int r ) {
++ freq;
int ils = 0; splitASdrug ( l, ils );
int aim = ils; splitASdrug ( r, ils );
for ( int i = 1; i <= aim; ++ i ) {
for ( int j = aim + 1; j <= ils; ++ j ) transASsub ( itls[i].l, itls[i].r, itls[j].l, itls[j].r, freq );
}
}
void add1 ( const int x ) { cur += buc2[col[x]], buc1[col[x]] ++; }
void add2 ( const int x ) { cur += buc1[col[x]], buc2[col[x]] ++; }
void sub1 ( const int x ) { cur -= buc2[col[x]], buc1[col[x]] --; }
void sub2 ( const int x ) { cur -= buc1[col[x]], buc2[col[x]] --; }
void captainMO () {
int nowl = 0, nowr = 0;
for ( int i = 1; i <= m; ++ i ) {
for ( ; nowl < asq[i].l; add1 ( ++ nowl ) ) ;
for ( ; nowr < asq[i].r; add2 ( ++ nowr ) ) ;
for ( ; nowl > asq[i].l; sub1 ( nowl -- ) ) ;
for ( ; nowr > asq[i].r; sub2 ( nowr -- ) ) ;
ans[asq[i].ID] += cur * asq[i].x;
}
}
int main () {
n = rint (); int _waste_ = rint ();
for ( int i = 1; i <= n; ++ i ) a[i] = pri[i] = rint ();
for ( int i = 1; i < n; ++ i ) {
int u = rint (), v = rint ();
addE ( u, v ), addE ( v, u );
}
initial (), rt = 1;
for ( int i = 1; i <= _waste_; ++ i ) {
int c = rint (), x, y;
if ( c == 1 ) rt = rint ();
else x = rint (), y = rint (), transASmany ( x, y );
}
sort ( asq + 1, asq + 1 + m, existcmp ), captainMO ();
for ( int i = 1; i <= freq; ++ i ) wint ( ans[i] ), putchar ( '\n' );
return 0;
}