给你一棵nn个节点的树,有mm次操作,操作包含以下三种:

  1. 新建一个从uuvv的任务,权值为ww
  2. 删除第ii个任务
  3. 询问所有不经过 的任务中最大的权值

n105,m2105n\le 10^5, m\le 2*10^5

LOJ 2049

Solution

考虑树剖,树上的一条路经转化为 dfs序上的 O(logn)O(\log n)个区间。

因为只要求不经过某个点任务的最大权值,所以只需要对每个点维护不经过它的任务即可,即对这个任务的补集进行操作。显然,补集区间个数也是O(logn)O(\log n)级别的

要支持删除,直接在线段树里用可删除堆维护即可(或者我一开始想的是线段树分治,但是常数太太太大需要大力卡常。。)

总复杂度O(nlog3n)O(n\log^3 n)

Code

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100, Maxm = Maxn << 1;

int N, M;
vector <int> G[Maxn];

struct query
{
int op, x, y, v;
} Q[Maxm];

struct Heap
{
priority_queue <int> Q1, Q2;

inline void process () { while (!Q2.empty() && Q1.top() == Q2.top()) Q1.pop(), Q2.pop(); }

inline void push (int x) { Q1.push(x); }

inline void erase (int x) { Q2.push(x); }

inline int top () { process (); return Q1.top(); }
};

namespace SEG
{
#define mid (l + r >> 1)
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
Heap node [Maxn << 2];

inline void build (int root, int l, int r)
{
node[root].push(-1);
if (l == r) return ;
build (lson), build (rson);
}

inline void update (int root, int l, int r, query x)
{
if (x.x > x.y) return ;
if (x.x <= l && r <= x.y)
{
if (!x.op) node[root].push (x.v);
else node[root].erase (x.v);
}
else
{
if (x.x <= mid) update (lson, x);
if (x.y > mid) update (rson, x);
}
}

inline int query (int root, int l, int r, int x)
{
if (l == r) return node[root].top();

if (x <= mid) return max (node[root].top(), query (lson, x));
else return max (node[root].top(), query (rson, x));
}

#undef mid
#undef lson
#undef rson
}

namespace HLD
{
int fa[Maxn], size[Maxn], dep[Maxn], top[Maxn], dfn[Maxn], son[Maxn], dfs_clock;

inline void dfs_pre (int x)
{
size[x] = 1, dep[x] = dep[fa[x]] + 1;

for (int i = 0; i < G[x].size(); ++i)
{
int y = G[x][i];
if (y == fa[x]) continue;
fa[y] = x;
dfs_pre (y);

if (size[y] > size[son[x]]) son[x] = y;
size[x] += size[y];
}
}

inline void get_top (int x, int now)
{
top[x] = now, dfn[x] = ++dfs_clock;
if (son[x]) get_top (son[x], now);

for (int i = 0; i < G[x].size(); ++i)
{
int y = G[x][i];
if (y == fa[x] || y == son[x]) continue;
get_top (y, y);
}
}

inline void init () { dfs_pre(1), get_top(1, 1); }

pii Seg[Maxn];
int seg_cnt = 0;

inline void update (query now)
{
int x = now.x, y = now.y;
seg_cnt = 0;

while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]]) swap(x, y);
Seg[++seg_cnt] = mp(dfn[top[x]], dfn[x]);
x = fa[top[x]];
}

if (dep[x] > dep[y]) swap(x, y);
Seg[++seg_cnt] = mp(dfn[x], dfn[y]);
Seg[++seg_cnt] = mp(N + 1, N + 1);

sort(Seg + 1, Seg + seg_cnt + 1);

for (int i = 1; i <= seg_cnt; ++i)
SEG :: update (1, 1, N, (query){now.op, Seg[i - 1].y + 1, Seg[i].x - 1, now.v});
}

inline int query (int x) { return SEG :: query (1, 1, N, dfn[x]); }
}

inline void Solve ()
{
HLD :: init ();
SEG :: build (1, 1, N);

for (int i = 1; i <= M; ++i)
{
int op = read<int>(), x = read<int>();
if (!op)
{
int y = read<int>(), v = read<int>();
Q[i] = (query){op, x, y, v};
HLD :: update (Q[i]);
}
else if (op == 1) Q[x].op = 1, HLD :: update (Q[x]);
else printf("%d\n", HLD :: query (x));
}
}

inline void Input ()
{
N = read<int>(), M = read<int>();
for (int i = 1; i < N; ++i)
{
int x = read<int>(), y = read<int>();
G[x].pb(y), G[y].pb(x);
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}

x