杭电多校03 HDU-6765 Count on a Tree II Striking Back(概率论，树链剖分)
Problem Description
You are given a tree with n nodes. The tree nodes are numbered from 1 to n. The color of the i-th node is coli.
You need to perform the following operations for m times:
· "1 x y" (1≤x,y≤n): Change the color of the x-th node into y.
· "2 a b c d" (1≤a,b,c,d≤n): Let's denote f(u,v) as the number of different colors occured on the path from u to v. You need to answer whether f(a,b)>f(c,d) is true.
题意：
给定一个含有(mathit n) 个节点的树，每一个节点上有一个数字代表该节点的颜色，
你需要做以下两种操作：
1、将节点$mathit x $ 颜色改为(mathit y)。
2、问((a,b))路径中不同颜色的节点个数是否比((c,d))路径多。
输入的数据中，(x,y,a,b,c,d)都被异或加密了，即强制在线处理。
思路：
首先要知道一个结论：
(mathit k)个([0,1])的随机实数的最小值的期望为(frac{1}{k+1})。
证明：
设随机数的最小值为(mathit x)，即k次随机中，有一次是x，剩下的k-1次都是大于等于x的，
则(E(x)=x*P(x)=x*int_{0}^{1} k*(1-x)^{k-1}\, dx)。
那么对于一个大小为 k 的集合，如果给每个元素随机一个正整数，那么多次采样得到的平均最小值越小就说明 k 的值越大。
回到本题，因为题目保证：It is guaranteed that f(a,b)≥2f(c,d) or f(c,d)≥2f(a,b) always holds for each query.
所以我们可以进行 k 次采样，每次采样时对每种颜色随机一个正整数，令每个点的点权为其
颜色对应的随机数，然后统计询问的树链上点权的最小值，将 k 次采样的结果相加以粗略比较
两条树链的颜色数的大小，因为不要求精确值所以 k 取几十即可得到正确结果。
使用树链剖分 + 线段树的时间复杂度为 O(nk + mklog 2 n)，使用全局平衡二叉树可以做
到 O(nk + mklogn)。
这里我先贴一个树链剖分 + 线段树的代码，全局平衡二叉树回头补上。
注意问题要注意一下几点，
(n*k)次随机数，大概需要(1e7)次随机，这里必须要用性能较好，循环节特别大的随机数生成器。
我自测了一下，(rand())是过不了的，(mt19937)大概需要(k=40)才能过，(xorshift128())大概(k=30)即可通过本题。
线段树+树剖代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), ' ', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("
");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("
");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '
' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '
' : ' ');}}
const int maxn = 600010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
namespace IStream {
const int L = 1 << 15;
char buffer[L + 5], *s, *t;
inline char get_char() {
if (s == t) {
t = (s = buffer) + fread(buffer, 1, L, stdin);
if (s == t) return EOF;
} return *s++;
}
inline int get_int() {
char c; int ret = 0;
while (c = get_char(), c < '0' || c > '9') ;
while (c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + (c - '0'), c = get_char();
return ret;
}
};
int n, m;
int root;
int a[maxn];// 初始点权
int wt[maxn];// 新建编号点权。
int cnt;// 编号用的变量
int top[maxn];// 所在重链的顶点编号
int id[maxn];//节点的新编号。
std::vector<int> son[maxn];
int SZ[maxn];// 子数大小
int wson[maxn];// 重儿子
int fa[maxn];// 父节点
int dep[maxn];// 节点的深度
void init()
{
cnt = 0;
repd(i, 1, n)
{
son[i].clear();
wson[i] = 0;
top[i] = 0;
id[i] = 0;
SZ[i] = 0;
fa[i] = 0;
dep[i] = 0;
}
}
void dfs1(int id, int pre, int step) // 维护出sz,wson,fa,dep
{
dep[id] = step;
fa[id] = pre;
SZ[id] = 1;
int maxson = -1;
for (auto x : son[id])
{
if (x != pre)
{
dfs1(x, id, step + 1);
SZ[id] += SZ[x];
if (SZ[x] > maxson)
{
maxson = SZ[x];
wson[id] = x;
}
}
}
}
//处理出top[],wt[],id[]
void dfs2(int u, int far, int topf)
{
assert(u <= n && u >= 1);
id[u] = ++cnt;
wt[cnt] = a[u];
top[u] = topf;
if (!wson[u]) // 没儿子时直接结束
{
return ;
}
dfs2(wson[u], u, topf); // 先处理重儿子
for (auto x : son[u])
{
if (x == wson[u] || x == far) //只处理轻儿子
{
continue;
}
dfs2(x, u, x); // 每个轻儿子以自己为top
}
}
typedef unsigned int U;
const int K = 30;
int k = K;
U temp[K];
U w[maxn][K];
U segment_tree[maxn << 2][K];
void build(int rt, int l, int r)
{
if (l == r)
{
rep(i, 0, K)
{
segment_tree[rt][i] = w[wt[l]][i];
}
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
rep(i, 0, K)
{
segment_tree[rt][i] = min(segment_tree[rt << 1][i] , segment_tree[rt << 1 | 1][i]) ;
}
}
void update(int rt, int l, int r, int x, int val)
{
if (l == x && r == x)
{
rep(i, 0, K)
{
segment_tree[rt][i] = w[val][i];
}
return ;
}
int mid = (l + r) >> 1;
if (x > mid)
{
update(rt << 1 | 1, mid + 1, r, x, val);
} else
{
update(rt << 1, l, mid , x, val);
}
rep(i, 0, K)
{
segment_tree[rt][i] = min(segment_tree[rt << 1][i] , segment_tree[rt << 1 | 1][i]) ;
}
}
void query(int rt, int tl, int tr, int l, int r)
{
if (tl >= l && tr <= r)
{
rep(i, 0, k) {
temp[i] = min(temp[i], segment_tree[rt][i]);
}
return ;
}
int mid = (tl + tr) >> 1;
if (mid >= l)
{
query(rt << 1, tl, mid, l, r);
}
if (mid < r)
{
query(rt << 1 | 1, mid + 1, tr, l, r);
}
}
ll qrange(int x, int y)
{
ll ans = 0ll;
rep(i, 0, K)
{
temp[i] = inf;
}
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
{
swap(x, y);
}
query(1, 1, n, id[top[x]], id[x]);
x = fa[top[x]];
}
if (dep[x] > dep[y])
swap(x, y);
query(1, 1, n, id[x], id[y]);
rep(i, 0, K)
{
ans += temp[i];
}
return ans;
}
U SX = 335634763, SY = 873658265, ssz = 192849106, SW = 746126501;
inline U xorshift128() {
U t = SX ^ (SX << 11);
SX = SY;
SY = ssz;
ssz = SW;
return SW = SW ^ (SW >> 19)^t ^ (t >> 8);
}
int main()
{
// freopen("C:\code\input.txt", "r", stdin);
int t;
mt19937 rnd(time(0));
repd(i, 1, maxn - 1)
{
rep(j, 0, k)
w[i][j] = xorshift128();
}
t = IStream::get_int();
root = 1;
while (t--)
{
n = IStream::get_int();
m = IStream::get_int();
init();
repd(i, 1, n)
{
a[i] = IStream::get_int();
}
int u, v;
repd(i, 2, n)
{
u = IStream::get_int(); v = IStream::get_int();
son[u].pb(v);
son[v].pb(u);
}
dfs1(1, 0, 1);
dfs2(1, 1, 1);
build(1, 1, n);
int op, x, y, c, d;
int cnt_yes = 0;
while (m--)
{
op = IStream::get_int();
if (op == 1)
{
x = IStream::get_int();
y = IStream::get_int();
x ^= cnt_yes;
y ^= cnt_yes;
update(1, 1, n, id[x], y);
} else
{
x = IStream::get_int();
y = IStream::get_int();
c = IStream::get_int();
d = IStream::get_int();
x ^= cnt_yes;
y ^= cnt_yes;
c ^= cnt_yes;
d ^= cnt_yes;
ll sum1 = 0ll, sum2 = 0ll;
sum1 = qrange(x, y);
sum2 = qrange(c, d);
if (sum1 < sum2)
{
puts("Yes");
cnt_yes++;
} else
{
puts("No");
}
}
}
}
return 0;
}