「YNOI2016」自己的发明
不换根
基本的莫队吧...
子树直接转到dfs序上。
其余部分可以见 「SNOI2017」一个简单的询问。
换根
根root，查询x，分3种：
- root不在x子树内，按照原来dfs序区间即可
- root在x子树内且root！=x，那么就是整个序列除掉H（root的祖先，且为x儿子）对应的dfs序区间
- root=x
直接将序列扩展就可以了，常数共(8 sqrt 2)。
优化
若H对应区间为([l,r])时，那么答案为(cnt[1,l-1] + cnt[r+1,n]=(cnt[1,n]-cnt[l,r]))，再乘上另一个区间。
那么可以预处理出([1,x])与([1,n])的答案。
这样每个询问只需要做一次([l,r])和([l1,r1])的查询了，常数4。
但是，实际上不没有快多少...
对2e6个询问排序，复杂度极高。
因此，可以用vector存每个左端点块对应询问，再排序。
效果明显（！
倍增过程可以去掉，每个点用vector存儿子dfn序，若将子树中某点跳到该点的某个儿子，可以在该点直接二分一下。
只快了一点...
#include <bits/stdc++.h>
#define rep(q, a, b) for (int q = a, q##_end_ = b; q <= q##_end_; ++q)
#define dep(q, a, b) for (int q = a, q##_end_ = b; q >= q##_end_; --q)
#define mem(a, b) memset(a, b, sizeof a)
#define debug(a) cerr << #a << ' ' << a << "___" << endl
using namespace std;
bool cur1;
char buf[10000000], *p1 = buf, *p2 = buf;
#define Getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1++
void in(int &r) {
static char c;
r = 0;
while (c = Getchar(), c < 48)
;
do
r = (r << 1) + (r << 3) + (c ^ 48);
while (c = Getchar(), c > 47);
}
const int mn = 100005;
const int mm = 500005;
int K, n, m, vl[mn], val[mn];
int head[mn], ne[mn << 1], to[mn << 1], cnt2;
#define link(a, b) link_edge(a, b), link_edge(b, a)
#define link_edge(a, b) to[++cnt2] = b, ne[cnt2] = head[a], head[a] = cnt2
#define travel(x) for (int q(head[x]); q; q = ne[q])
int ind, dfn_l[mn], dfn_r[mn];
vector<int> son[mn];
int mp[mn];
void dfs(int f, int x) {
++ind, mp[ind]=x,val[ind] = vl[x], dfn_l[x] = ind;
travel(x) if (to[q] != f) dfs(x, to[q]),son[x].push_back(dfn_l[to[q]]);
dfn_r[x] = ind;
}
int get_high(int x, int v) {
int l=0,r=(int)son[x].size()-1,ans=0;
while(l<=r){
int mid=l+r>>1;
if(son[x][mid]>v)r=mid-1;
else l=mid+1,ans=mid;
}
return mp[son[x][ans]];
}
long long ans[mm];
struct node {
int l, r, id;
inline bool operator<(const node &A) const { return r < A.r; }
};
inline bool cmp(node a, node b) { return a.r > b.r; }
vector<node> an[800];
int cnt[mn], cnt1[mn];
bool mark[mm];
long long mid_ans, mid[mn];
void init() {
dfs(0, 1);
sort(mid + 1, mid + n + 1);
rep(q, 1, n) val[q] = lower_bound(mid + 1, mid + n + 1, val[q]) - mid;
rep(q, 1, n)++ cnt[val[q]];
rep(q, 1, n) mid[q] = mid[q - 1] + cnt[val[q]];
rep(q, 1, n)-- cnt[val[q]];
}
int find(int rt, int x) {
if (dfn_l[rt] >= dfn_l[x] && dfn_l[rt] <= dfn_r[x])
return get_high(x, dfn_l[rt]);
return 0;
}
bool cur2;
int main() {
// cerr<<(&cur2-&cur1)/1024.0/1024<<endl;
int td, l, r, l1, r1;
in(n), in(m);
rep(q, 1, n) in(vl[q]), mid[q] = vl[q];
rep(q, 2, n) in(l), in(r), link(l, r);
init();
K = n / sqrt(m)*1.2 + 1;
int rt = 1;
rep(q, 1, m) {
in(td);
if (td == 1)
in(rt);
else {
mark[q] = 1;
in(l), in(l1);
if (rt == l || rt == l1) {
if (rt == l1)
swap(l, l1);
if (rt == l1)
ans[q] = mid[n];
else {
int at = find(rt, l1);
if (at)
ans[q] = mid[n] - (mid[dfn_r[at]] - mid[dfn_l[at] - 1]);
else
ans[q] = mid[dfn_r[l1]] - mid[dfn_l[l1] - 1];
}
} else {
int at = find(rt, l), at1 = find(rt, l1);
if (!at)
swap(at, at1), swap(l, l1);
td = 1;
if (at && !at1)
ans[q] = mid[dfn_r[l1]] - mid[dfn_l[l1] - 1], td = -1, l = at;
else if (at1)
ans[q] = mid[n] - (mid[dfn_r[at]] - mid[dfn_l[at] - 1]) -
(mid[dfn_r[at1]] - mid[dfn_l[at1] - 1]),
l = at, l1 = at1;
r = dfn_r[l], l = dfn_l[l];
r1 = dfn_r[l1], l1 = dfn_l[l1];
an[r / K].push_back({ r, r1, q * td });
if (l > 1) {
an[min(r1, l - 1) / K].push_back({ min(r1, (l - 1)), max(r1, (l - 1)), -q * td });
if (l1 > 1)
an[min(l - 1, l1 - 1) / K].push_back(
{ min(l - 1, l1 - 1), max(l - 1, l1 - 1), q * td });
}
if (l1 > 1)
an[min(r, l1 - 1) / K].push_back({ min(r, l1 - 1), max(r, l1 - 1), -q * td });
}
}
}
l = 0, r = 0;
rep(q, 0, n / K) {
if (q & 1)
sort(an[q].begin(), an[q].end(), cmp);
else
sort(an[q].begin(), an[q].end());
rep(w, 0, (int)an[q].size() - 1) {
l1 = an[q][w].l, r1 = an[q][w].r;
while (l > l1) mid_ans -= cnt1[val[l]], --cnt[val[l--]];
while (r < r1) mid_ans += cnt[val[++r]], ++cnt1[val[r]];
while (l < l1) mid_ans += cnt1[val[++l]], ++cnt[val[l]];
while (r > r1) mid_ans -= cnt[val[r]], --cnt1[val[r--]];
an[q][w].id < 0 ? ans[-an[q][w].id] -= mid_ans : ans[an[q][w].id] += mid_ans;
}
}
rep(q, 1, m) if (mark[q]) printf("%lld
", ans[q]);
return 0;
}