2295. [HZOI 2015]榴莲

★★☆   输入文件： Durio_zibethinus_Murr.in   输出文件： Durio_zibethinus_Murr.out    简单对比 时间限制：1 s   内存限制：512 MB

【题目描述】

众所周知，榴莲长在树上，同时榴莲很臭

现在给定你一棵榴莲树，树根为1

要求你维护以下操作：

1、 1 u v w 树上长出一个榴莲，臭味度为w，臭味弥漫了树上u到v的简单路径上所有点

2、 2 u w 树上长出一个榴莲，臭味度为w，臭味弥漫了树上u的子树的所有点

3、 3 k  树上k时刻长出的榴莲从树上掉了下来，它所造成的臭味效果消失

4、 4 u k 询问所有弥漫到u节点的榴莲臭味值的第k大

【输入格式】

第一行输入n，m表示节点总数和操作次数

以下n-1行u，v描述两个端点

以下m行，第i行表示第i个时刻的操作如题意所示

n,m<=100000

数据保证第三个操作掉下来的是存在的且尚未掉下来的榴莲

【输出格式】

对于每个询问

若弥漫到u节点的榴莲不足k个，则输出-1

否则输出对应的答案

【样例输入】

10 10

2 1

3 1

4 3

5 4

6 1

7 3

8 3

9 7

10 2

4 1 1

1 3 1 13881

3 2

2 10 12573

2 7 2522

1 10 7 7976

1 7 7 15696

4 2 1

1 3 4 14384

1 10 9 7398

【样例输出】

-1

7976

题解：整体二分+树状数组+树上差分

首先预处理出DFS序和LCA，设in[u]和out[u]是以u为根节点的子树的最小和最大的DFS序

对于修改操作，用树状数组维护贡献：

①链上操作(X,Y)：

这个操作等价于

a. 对X到根节点路径上所有点贡献+1

b. 对Y到根节点路径上所有点贡献+1

c. 对LCA(X, Y)到根节点路径上所有点贡献-1

d. 对LCA(X,Y)的父节点 par[LCA(X, Y)]到根节点路径上所有点贡献-1

②子树操作(X):这个操作等价于将DFS序为in[u]~out[u]之间的点贡献+1

我们可以二分答案m，之后扫一遍之前的操作我们只需要知道有多少个权值>=m的操作经过当前点u就可以了，如果k不超过在这个节点的贡献cnt，则放入右区间，否则将k-=cnt并放入左区间。最后判断一下k是否小于或等于0，是的话答案为m，否则为-1（没有k个臭味）

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int MX = 1e5 + 5; const LL inf = 0x3f3f3f3f3f3f3f3f; struct Tree { int n; vector <int> T; void init (int _n) { T.clear(); n = _n; T.resize(n + 1); } void add (int x, int v) { for (int i = x; i <= n; i += i & -i) T[i] += v; } int sum (int x) { if (x > n) x = n; int ret = 0; for (int i = x; i > 0; i -= i & -i) ret += T[i]; return ret; } } bt1, bt2; struct Query { int op, u, v, w, k, id; } que[MX], t1[MX], t2[MX]; struct Edge { int v, nxt; } E[MX * 2]; int head[MX], tot, ans[MX], h[MX], mark[MX]; void add(int u, int v) { E[tot].v = v; E[tot].nxt = head[u]; head[u] = tot++; } //ver:节点编号 deep：深度 first：点编号位置 dir：距离 int sz, ver[2 * MX], deep[2 * MX], first[MX], dp[2 * MX][30], vis[MX], dir[MX]; int rear, seq[2 * MX], in[MX], out[MX], pre[MX]; void init(int n) { for (int i = 0; i <= n; i++) dir[i] = vis[i] = 0; sz = 0; } void dfs(int u, int dep, int fa) { vis[u] = true; ver[++sz] = u; first[u] = sz; deep[sz] = dep; seq[++rear] = u; in[u] = rear; pre[u] = fa; for (int i = head[u]; ~i ; i = E[i].nxt) { if ( vis[E[i].v] ) continue; int v = E[i].v; dir[v] = dir[u] + 1; dfs(v, dep + 1, u); ver[++sz] = u; deep[sz] = dep; } seq[++rear] = u; out[u] = rear; } void ST(int n) { for (int i = 1; i <= n; i++) dp[i][0] = i; for (int j = 1; (1 << j) <= n; j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) { int a = dp[i][j - 1], b = dp[i + (1 << (j - 1))][j - 1]; dp[i][j] = deep[a] < deep[b] ? a : b; } } } int RMQ(int l, int r) { int k = 0; while ((1 << (k + 1)) <= r - l + 1) k++; int a = dp[l][k], b = dp[r - (1 << k) + 1][k]; //保存的是编号 return deep[a] < deep[b] ? a : b; } int LCA(int u, int v) { int x = first[u], y = first[v]; if (x > y) swap(x, y); int ret = RMQ(x, y); return ver[ret]; } void pre_solve(int n) { dir[1] = 1; dfs(1, 1, 0); ST(sz); } inline void update1(int u, int v, int lca, int val) { bt1.add(in[u], val); bt1.add(in[v], val); bt1.add(in[lca], -val); if (pre[lca]) bt1.add(in[pre[lca]], -val); } inline void update2(int u, int val) { bt2.add(in[u], val); bt2.add(out[u], -val); } void work1(int L, int R, int m) { for (int i = L, u, v, lca; i <= R; i++) { if (que[i].op == 1) { if (que[i].w == m) { update1(que[i].u, que[i].v, LCA(que[i].u, que[i].v), 1); mark[que[i].id] = i; } } if (que[i].op == 2) { if (que[i].w == m) { update2(que[i].u, 1); mark[que[i].id] = i; } } if (que[i].op == 3) { if (mark[que[i].k]) { int j = mark[que[i].k]; mark[que[j].id] = 0; if (que[j].op == 1) update1(que[j].u, que[j].v, LCA(que[j].u, que[j].v), -1); else update2(que[j].u, -1); } } if (que[i].op == 4) { u = que[i].u; int sum = bt1.sum(out[u]) - bt1.sum(in[u] - 1) + bt2.sum(in[u]); que[i].k -= sum; } } for (int i = L; i <= R; i++) { if (mark[que[i].id]) { if (que[i].op == 1) update1(que[i].u, que[i].v, LCA(que[i].u, que[i].v), -1); else update2(que[i].u, -1); } mark[que[i].id] = 0; } } void work2(int L, int R, int m, int &p1, int &p2) { p1 = 0, p2 = 0; for (int i = L, u, v, lca; i <= R; i++) { if (que[i].op == 1) { if (que[i].w < m) t1[p1++] = que[i]; else { update1(que[i].u, que[i].v, LCA(que[i].u, que[i].v), 1); t2[p2++] = que[i], mark[que[i].id] = i; } } if (que[i].op == 2) { if (que[i].w < m) t1[p1++] = que[i]; else { update2(que[i].u, 1); t2[p2++] = que[i], mark[que[i].id] = i; } } if (que[i].op == 3) { if (!mark[que[i].k]) t1[p1++] = que[i]; else { int j = mark[que[i].k]; mark[que[i].k] = 0; if (que[j].op == 1) update1(que[j].u, que[j].v, LCA(que[j].u, que[j].v), -1); else update2(que[j].u, -1); t2[p2++] = que[i]; } } if (que[i].op == 4) { u = que[i].u; int sum = bt1.sum(out[u]) - bt1.sum(in[u] - 1) + bt2.sum(in[u]); if (sum < que[i].k) que[i].k -= sum, t1[p1++] = que[i]; else t2[p2++] = que[i]; } } for (int i = 0; i < p1; i++) que[L + i] = t1[i], mark[t1[i].id] = 0; for (int i = 0; i < p2; i++) { if (mark[t2[i].id]) { if (t2[i].op == 1) update1(t2[i].u, t2[i].v, LCA(t2[i].u, t2[i].v), -1); else update2(t2[i].u, -1); } que[L + p1 + i] = t2[i], mark[t2[i].id] = 0; } } void solve(int L, int R, int l, int r) { if (L > R || l > r) return; if (l == r) { work1(L, R, l); for (int i = L; i <= R; i++) { if (que[i].op != 4) continue; if (que[i].k <= 0) ans[que[i].id] = h[l]; else ans[que[i].id] = -1; } return; } int m = (l + r + 1) >> 1, p1, p2; work2(L, R, m, p1, p2); solve(L, L + p1 - 1, l, m - 1); solve(L + p1, R, m, r); } int main() { //freopen("in.txt", "r", stdin); freopen("Durio_zibethinus_Murr.in", "r", stdin); freopen("Durio_zibethinus_Murr.out", "w+", stdout); int n, m; scanf("%d%d", &n, &m); memset(head, -1, sizeof(head)); for (int i = 1, u, v; i < n; i++) scanf("%d%d", &u, &v), add(u, v), add(v, u); pre_solve(n); bt1.init(rear); bt2.init(rear); int mx = 0, cnt = 0; for (int i = 1; i <= m; i++) { scanf("%d", &que[i].op); if (que[i].op == 1) scanf("%d%d%d", &que[i].u, &que[i].v, &que[i].w), h[++cnt] = que[i].w, mx = max(que[i].w, mx); if (que[i].op == 2) scanf("%d%d", &que[i].u, &que[i].w), h[++cnt] = que[i].w, mx = max(que[i].w, mx); if (que[i].op == 3) scanf("%d", &que[i].k); if (que[i].op == 4) scanf("%d%d", &que[i].u, &que[i].k); que[i].id = i; ans[i] = -2; } sort(h + 1, h + cnt + 1); cnt = unique(h + 1, h + cnt + 1) - h - 1; for (int i = 1; i <= m; i++) if (que[i].op == 1 || que[i].op == 2) que[i].w = lower_bound(h + 1, h + cnt + 1, que[i].w) - h; solve(1, m, 0, mx); for (int i = 1; i <= m; i++) if (ans[i] >= -1)printf("%d\n", ans[i]); return 0; }