temp

做题记录 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
constexpr int N = 500005;
int n, p[N], k[N];
struct Edge { int to, nxt, w; } edgs[N << 1]; int head[N];
int cnt[N], dep[N], dis[N], hson[N], fa[N]; // dis: 节点 1 到 i 的距离
int dfntop=0, dfn[N], dfnmap[N], disdfn[N];
struct Chain { int head, rear; } chain[N]; // The point i belongs to chain: head[i] .. rear[i]
void dfs1(int u, int pre) { // Get cnt, dep, dis, hson, fa
    cnt[u] = 1, fa[u] = pre;
    for (int i = head[u], v; i; i = edgs[i].nxt) {
        if ((v = edgs[i].to) == pre) continue;
        dep[v] = dep[u] + 1, dis[v] = dis[u] + edgs[i].w;
        dfs1(v, u);
        cnt[u] += cnt[v];
        if (cnt[v] > cnt[hson[u]]) hson[u] = v;
    }
}
void dfs2(int u, int top) { // Get dfn(map), chain
    dfn[u] = ++dfntop;
    dfnmap[dfn[u]] = u;
    disdfn[dfn[u]] = dis[u];
    chain[u] = {top, u};
    if (hson[u]) {
        dfs2(hson[u], top);
        chain[u].rear = chain[hson[u]].rear; // 更新链尾
        for (int i = head[u], v; i; i = edgs[i].nxt) {
            if ((v = edgs[i].to) == fa[u] || v == hson[u]) continue;
            dfs2(v, v);
        }
    }
}
namespace SegTree { // 按照 dfn 序编号，不是原编号
    using QueryRes = std::pair<int,int>;
    struct TopSet { // 大根可删堆
        inline void push(int x) { qadd.push(x); }
        inline void erase(int x) { qdel.push(x); }
        inline int top() { // Without no_throw
            while (qadd.top() == qdel.top())
                qadd.pop(), qdel.pop();
            return qadd.top();
        }
    private:
        std::priority_queue<int> qadd, qdel;
    } base[N];
    int mx[N << 2], mn[N << 2];
    int flglazy[N]; // 覆盖次数（加入 +1，删除 -1）
    bool flg[N << 2]; // 是否被覆盖
    int modify_pos, modify_l, modify_r, modify_val;
    bool modify_type;
    void upd1(int u, int l, int r) {
        if (l == r) {
            modify_type ? base[u].push(modify_val) : base[u].erase(modify_val);
            mn[u] = dis[u] + base[u].top();
            mx[u] = dis[u] - base[u].top();
        } else {
            int mid = (l + r) >> 1;
            if (modify_pos <= mid) upd1(u<<1, l, mid);
            else upd1(u<<1|1, mid+1, r);
            mx[u] = std::max(mx[u<<1], mx[u<<1|1]);
            mn[u] = std::min(mn[u<<1], mn[u<<1|1]);
        }
    }
    void upd2(int u, int l, int r) {
        if (modify_l <= l && r <= modify_r)
            flg[u] = flglazy[u] += modify_val; // 看看还有没有可用覆盖了
        else {
            int mid = (l + r) >> 1;
            if (modify_l <= mid) upd2(u<<1, l, mid);
            if (mid < modify_r) upd2(u<<1|1, mid+1, r);
            flg[u] = flg[u<<1] && flg[u<<1|1];
        }
    }
    inline void helper_updres(QueryRes &q, const QueryRes &x) {
        q.first = std::min(q.first, x.first);
        q.second = std::max(q.second, x.second);
    }
    int query_l, query_r;
    QueryRes query1(int u, int l, int r) {
        if (query_l <= l && r <= query_r) return QueryRes(mn[u], mx[u]);
        int mid = (l + r) >> 1;
        QueryRes res(1 << 30, 0);
        if (query_l <= mid) helper_updres(res, query1(u<<1, l, mid));
        if (mid < query_r) helper_updres(res, query1(u<<1|1, mid+1, r));
        return res;
    }
    bool query2(int u, int l, int r) {
        if (flg[u]) return true; // 这一整块都合法
        if (query_l <= l && r <= query_r) return false;
        int mid = (l + r) >> 1;
        if (query_l <= mid && !query2(u<<1, l, mid)) return false;
        if (mid < query_r && !query2(u<<1|1, mid+1, r)) return false;
        return true;
    }
    
    /// @brief 更改某一个节点的关键属性
    /// @param u 节点的下标（原顺序，非dfn序）
    /// @param x 设置为`k=x`的关键点
    /// @param f [true] 加入 [false] 删除
    inline void change(int u, int x, bool f) {
        modify_type = f;
        while (u && x >= 0) { // 子树可以直接更新 (dfn 连续)，核心是更新 祖先
            modify_pos = dfn[u], modify_val = x;
            upd1(1, 1, n); // 更新 u 的最大最小
        #define All disdfn + dfn[chain[u].head], disdfn + dfn[chain[u].rear] + 1 // 当前重链上的所有距离(严格递增，按照 dfn 序)
            modify_l = std::lower_bound(All, dis[u] - x) - disdfn; // 二分查找在重链上的影响范围
            modify_r = std::upper_bound(All, dis[u] + x) - disdfn - 1;
            modify_val = f ? 1 : -1;
            if (modify_l <= modify_r) upd2(1, 1, n); // 更新影响范围
        #undef All
            x -= dis[fa[chain[u].head]] - dis[u]; // 减去深度
            u = fa[chain[u].head]; // 跳重链
        }
    }

    /// @brief 查询 dfn l-r 节点能到达的最远地
    /// @return `(最浅层, 最深层)`
    inline QueryRes ask(int l, int r) {
        query_l = l, query_r = r;
        return query1(1, 1, n);
    }

    /// @brief 查询 dfn l-r 节点是否`全部`被关键点覆盖
    inline bool askcov(int l, int r) {
        query_l = l, query_r = r;
        return query2(1, 1, n);
    }
} using SegTree::change;
int main() {
    freopen("secure.in", "r", stdin);
    freopen("secure.out", "w", stdout);
    int m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1, u, v, w; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        edgs[++head[0]] = Edge {u, head[v], w}; head[v] = head[0];
        edgs[++head[0]] = Edge {v, head[u], w}; head[u] = head[0];
    }
    dfs1(1, 0); dfs2(1, 1);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &p[i], &k[i]);
        change(p[i], k[i], true);
    }
    for (int op, x, y; q--; ) {
        scanf("%d%d", &op, &x);
        switch (op) {
        case 1: {
            scanf("%d", &y);
            change(x, y, true);
            ++m, p[m] = x, k[m] = y;
            break;
        }
        case 2: {
            change(p[x], k[x], false);
            break;
        }
        }
    }
    return 0;
}