题面
题解
带修改的主席树？？？我可没有那么勤快去写个树套树
只要它不强制在线，我就可以用整体二分做
思路大致与【ZJOI2013】K大数查询相似
只不过放在树上做，还带修改
同样处理出询问，并且一个修改操作要拆分成两个
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data*w;
}
const int maxn(80010);
struct edge { int next, to; } e[maxn << 1];
int head[maxn], e_num, n, q;
inline void add_edge(int from, int to) { e[++e_num] = (edge) {head[from], to}; head[from] = e_num; }
int pos[maxn], fa[maxn], size[maxn], heavy[maxn], belong[maxn], dep[maxn], cnt;
void dfs(int x)
{
size[x] = 1;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa[x]) continue;
fa[to] = x; dep[to] = dep[x] + 1; dfs(to);
size[x] += size[to];
if(size[heavy[x]] < size[to]) heavy[x] = to;
}
}
void dfs(int x, int chain)
{
pos[x] = ++cnt; belong[x] = chain;
if(!heavy[x]) return;
dfs(heavy[x], chain);
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa[x] || to == heavy[x]) continue;
dfs(to, to);
}
}
int sum, ans[maxn], c[maxn], T[maxn];
struct qry { int k, a, b, id, opt; } p[maxn << 1], pl[maxn << 1], pr[maxn << 1];
inline void add(int x, int v) { while(x <= n) c[x] += v, x += x & -x; }
inline int query(int x) { int ans = 0; while(x) ans += c[x], x -= x & -x; return ans; }
inline int LCA(int a, int b)
{
while(belong[a] ^ belong[b])
{
if(pos[belong[a]] < pos[belong[b]]) std::swap(a, b);
a = fa[belong[a]];
}
return pos[a] < pos[b] ? a : b;
}
inline int Query(int a, int b)
{
int ans = 0;
while(belong[a] ^ belong[b])
{
if(pos[belong[a]] < pos[belong[b]]) std::swap(a, b);
ans += query(pos[a]) - query(pos[belong[a]] - 1);
a = fa[belong[a]];
}
if(pos[a] < pos[b]) std::swap(a, b);
return ans + query(pos[a]) - query(pos[b] - 1);
}
void Div(int l, int r, int ql, int qr)
{
if(ql > qr) return;
if(l == r) { for(RG int i = ql; i <= qr; i++) if((!p[i].opt) && (~ans[p[i].id])) ans[p[i].id] = l; return; }
int mid = (l + r) >> 1, tl = 0, tr = 0;
for(RG int i = ql; i <= qr; i++)
{
if(p[i].k == 0)
if(p[i].b <= mid) pl[++tl] = p[i];
else pr[++tr] = p[i], add(pos[p[i].a], p[i].id);
else
{
int sum = Query(p[i].a, p[i].b);
if(sum >= p[i].k) pr[++tr] = p[i];
else p[i].k -= sum, pl[++tl] = p[i];
}
}
for(RG int i = ql; i <= qr; i++) if(p[i].opt && p[i].b > mid) add(pos[p[i].a], -p[i].id);
for(RG int i = 1; i <= tl; i++) p[ql + i - 1] = pl[i];
for(RG int i = 1; i <= tr; i++) p[ql + tl + i - 1] = pr[i];
Div(l, mid, ql, ql + tl - 1); Div(mid + 1, r, ql + tl, qr);
}
int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
n = read(); q = read(); int tot = 0;
for(RG int i = 1; i <= n; i++) p[++tot] = (qry) {0, i, T[i] = read(), 1, 1};
for(RG int i = 1, a, b; i < n; i++)
a = read(), b = read(), add_edge(a, b), add_edge(b, a);
dfs(1); dfs(1, 1);
for(RG int i = 1, k, a, b; i <= q; i++)
{
k = read(); a = read(); b = read();
if(k)
{
p[++tot] = (qry) {k, a, b, ++sum, 0};
int dis = dep[a] + dep[b] - (dep[LCA(a, b)] << 1) + 1;
if(p[tot].k > dis) ans[p[tot].id] = -1;
}
else p[++tot] = (qry) {0, a, T[a], -1, 1}, p[++tot] = (qry) {0, a, T[a] = b, 1, 1};
}
Div(1, 100000000, 1, tot);
for(RG int i = 1; i <= sum; i++)
(~ans[i]) ? printf("%d
", ans[i]) : puts("invalid request!");
return 0;
}