题解 P3703 【[SDOI2017]树点涂色】
怎么题解全是LCT，我树剖不服
第一个操作就是树链覆盖，放到序列上就是区间合并，区间合并暴力的时间复杂度是均摊
线段树上维护一个节点到根节点的权值
那么第二个操作就是
第三个操作线段树区间最值
没了
时间复杂度:
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define DEBUG(args...) fprintf(stderr, args)
typedef long long LL;
#define FOR(i, l, r) for(int i = (l), i##_end = (r); i <= i##_end; ++i)
#define REP(i, l, r) for(int i = (l), i##_end = (r); i < i##_end; ++i)
#define DFR(i, l, r) for(int i = (l), i##_end = (r); i >= i##_end; --i)
#define DRP(i, l, r) for(int i = (l), i##_end = (r); i > i##_end; --i)
template<class T>T Min(const T &a, const T &b) {return a < b ? a : b;}
template<class T>T Max(const T &a, const T &b) {return a > b ? a : b;}
template<class T>bool Chkmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T>bool Chkmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
class fast_input {
private:
static const int SIZE = 1 << 15 | 1;
char buf[SIZE], *front, *back;
void Next(char &c) {
if(front == back) back = (front = buf) + fread(buf, 1, SIZE, stdin);
c = front == back ? (char)EOF : *front++;
}
public :
template<class T>void operator () (T &x) {
char c, f = 1;
for(Next(c); !isdigit(c); Next(c)) if(c == '-') f = -1;
for(x = 0; isdigit(c); Next(c)) x = x * 10 + c - '0';
x *= f;
}
void operator () (char &c, char l = 'a', char r = 'z') {
for(Next(c); c > r || c < l; Next(c)) ;
}
}input;
const int SN = 100000 + 47;
const int ST = SN << 2 | 1;
const int SE = 200000 + 47;
const int SM = 200000 + 47;
int head[SN], nxt[SE], to[SE];
int col_top[SM], col_bot[SM], col_now;
int size[SN], son[SN], fa[SN], deep[SN];
int top[SN], f[SN], g[SN], h[SN], rank;
int max[ST], tag[ST], col[ST];
int n;
void Add(int, int);
void DFS(int);
void DFS(int, int);
void Build(int, int, int);
void Update(int);
void Modify(int, int, int, int, int, int);
void PushAdd(int, int);
void PushDown(int);
int Ask(int, int, int, int, int);
void ModifyCol(int, int, int, int, int, int);
int AskCol(int, int, int, int);
void Modify(int, int);
int Ask0(int, int);
int Ask1(int);
int __lp, __lq;
int LCA(int, int);
int main() {
#ifdef Cai
freopen("s.in", "r", stdin);
#endif
int m, x, y, z;
input(n), input(m);
FOR(i, 2, n) input(x), input(y), Add(x, y);
col_now = n;
FOR(i, 1, n) col_top[i] = col_bot[i] = i;
deep[1] = 1, DFS(1), DFS(1, -1), Build(1, 1, n);
while(m--) {
//DEBUG("[%d]\n", m);
input(x), input(y);
if(x == 1) Modify(y, ++col_now);
else if(x == 2) input(z), printf("%d\n", Ask0(y, z));
else printf("%d\n", Ask1(y));
}
return 0;
}
void Add(int x, int y) {
static int _ = 0;
nxt[++_] = head[x], head[x] = _, to[_] = y;
nxt[++_] = head[y], head[y] = _, to[_] = x;
}
void DFS(int x) {
size[x] = 1;
for(int i = head[x]; i; i = nxt[i])
if(to[i] != fa[x]) {
fa[to[i]] = x, deep[to[i]] = deep[x] + 1;
DFS(to[i]), size[x] += size[to[i]];
if(size[to[i]] > size[son[x]]) son[x] = to[i];
}
}
void DFS(int x, int y) {
top[x] = y, f[x] = ++rank, h[rank] = x;
if(son[x]) DFS(son[x], y);
for(int i = head[x]; i; i = nxt[i])
if(to[i] != fa[x] && to[i] != son[x])
DFS(to[i], to[i]);
g[x] = rank;
}
void Build(int rt, int l, int r) {
if(l == r) {max[rt] = deep[h[l]], tag[rt] = 0, col[rt] = h[l]; return ;}
int mid = l + r >> 1;
Build(rt << 1, l, mid), Build(rt << 1 | 1, mid + 1, r);
Update(rt);
}
void Update(int rt) {
max[rt] = Max(max[rt << 1], max[rt << 1 | 1]);
}
void Modify(int rt, int l, int r, int s, int t, int k) {
if(l == s && r == t) {PushAdd(rt, k); return ;}
PushDown(rt);
int mid = l + r >> 1;
if(t <= mid)
Modify(rt << 1, l, mid, s, t, k);
else if(s > mid)
Modify(rt << 1 | 1, mid + 1, r, s, t, k);
else {
Modify(rt << 1, l, mid, s, mid, k);
Modify(rt << 1 | 1, mid + 1, r, mid + 1, t, k);
}
Update(rt);
}
void PushAdd(int rt, int x) {
tag[rt] += x, max[rt] += x;
}
void PushDown(int rt) {
if(tag[rt]) PushAdd(rt << 1, tag[rt]), PushAdd(rt << 1 | 1, tag[rt]);
tag[rt] = 0;
}
int Ask(int rt, int l, int r, int s, int t) {
if(l == s && r == t) return max[rt];
PushDown(rt);
int mid = l + r >> 1;
if(t <= mid)
return Ask(rt << 1, l, mid, s, t);
else if(s > mid)
return Ask(rt << 1 | 1, mid + 1, r, s, t);
else
return Max(Ask(rt << 1, l, mid, s, mid),
Ask(rt << 1 | 1, mid + 1, r, mid + 1, t));
}
void ModifyCol(int rt, int l, int r, int s, int t, int k) {
if(l == s && r == t) {col[rt] = k; return ;}
int mid = l + r >> 1;
if(t <= mid)
ModifyCol(rt << 1, l, mid, s, t, k);
else if(s > mid)
ModifyCol(rt << 1 | 1, mid + 1, r, s, t, k);
else {
ModifyCol(rt << 1, l, mid, s, mid, k);
ModifyCol(rt << 1 | 1, mid + 1, r, mid + 1, t, k);
}
}
int AskCol(int rt, int l, int r, int p) {
if(l == r) return col[rt];
int mid = l + r >> 1;
if(p <= mid) return Max(col[rt], AskCol(rt << 1, l, mid, p));
else return Max(col[rt], AskCol(rt << 1 | 1, mid + 1, r, p));
}
void Modify(int x, int y) {
col_bot[y] = x, col_top[y] = 1;
int p, q, r, c, nl = 0, nr = 0, toplastc, nextx;
while(x) {
p = Ask(1, 1, n, f[x], f[x]);
c = AskCol(1, 1, n, f[x]);
r = col_top[c];
if(f[r] < f[top[x]]) {
ModifyCol(1, 1, n, f[top[x]], f[x], y);
Modify(1, 1, n, f[top[x]], g[top[x]], 1 - p);
if(nl) Modify(1, 1, n, nl, nr, p - 1);
}
else {
ModifyCol(1, 1, n, f[r], f[x], y);
Modify(1, 1, n, f[r], g[r], 1 - p);
if(nl) Modify(1, 1, n, nl, nr, p - 1);
}
if(col_bot[c] != x) {
LCA(col_bot[c], x); // __lp is a child of x, which col is c
if(f[__lp] != nl) {
Modify(1, 1, n, f[__lp], g[__lp], 1);
toplastc = __lp;
}
}
if(f[r] < f[top[x]])
nl = f[top[x]], nr = g[top[x]], x = fa[top[x]];
else
nl = f[r], nr = g[r], x = fa[r], col_top[c] = toplastc;
}
}
int Ask0(int x, int y) {
int lca = LCA(x, y);
int ans = Ask(1, 1, n, f[x], f[x]) + Ask(1, 1, n, f[y], f[y]);
ans -= 2 * Ask(1, 1, n, f[lca], f[lca]);
return ans + 1;
}
int Ask1(int x) {
return Ask(1, 1, n, f[x], g[x]);
}
int LCA(int x, int y) {
while(top[x] != top[y])
if(deep[top[x]] > deep[top[y]]) __lp = top[x], x = fa[top[x]];
else __lq = top[y], y = fa[top[y]];
if(x == y) return x;
if(deep[x] < deep[y]) return __lq = son[x], x;
return __lp = son[y], y;
}
/*
g++ -o s s.cpp -O2; for((i = 1; i <= 10; ++i)) do cp paint$i.in s.in; ./s > s.out; diff paint$i.out s.out -w > s.res; echo $?; done
*/