洛谷P4092 [HEOI2016/TJOI2016]树题解

题目链接：P4092 [HEOI2016/TJOI2016]树

题意：

在 1919 年，cxy 刚刚学习了树，非常开心。现在她想解决这样一个问题：给定一颗有根树，根为 $1$ ，有以下两种操作：

标记操作：对某个结点打上标记。（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）

询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先）

你能帮帮她吗？

输入格式：

第一行两个正整数 $N$ 和 $Q$ 分别表示节点个数和操作次数。

接下来 $N-1$ 行，每行两个正整数 $u,v\ (1 \le u,v \le n)$ 表示 $u$ 到 $v$ 有一条有向边。

接下来 $Q$ 行，形如 oper num ，oper 为 C 时表示这是一个标记操作， oper 为 Q 时表示这是一个询问操作。

输出格式：

输出一个正整数，表示结果.

数据范围：

$1 \le N, Q \le 10^5$ 。

注意到一个节点被标记后，它所在子树的答案都会被更新。

子树更新？考虑树剖。然后就没了，可能就只是个板子吧

时间复杂度 $\mathcal{O}(Q \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n,Q,pos=1,head[N],dep[N],id[N],fa[N];
int sz[N],son[N],top[N],val[N * 4], tag[N * 4];
struct Edge { int u,v,next; } e[N * 2];
void down2(int &x,int y) { dep[x] < dep[y] ? x = y : 0; }
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void dfs(int u,int f,int d)
{
    dep[u] = d; fa[u] = f; sz[u] = 1; int mx = -1;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == f) continue;
        dfs(v,u,d+1); sz[u] += sz[v]; if(sz[v] > mx) { mx = sz[u], son[u] = v; }
    }
}
void dfs(int u,int ftop)
{
    static int tim = 0; top[u] = ftop; id[u] = ++tim;
    if(son[u]) dfs(son[u], ftop);
    for(int i = head[u]; i; i = e[i].next)
    { int v = e[i].v; if(v != fa[u] && v != son[u]) dfs(v,v); }
}
void push_down(int at)
{
    if(tag[at] != 1)
    {
        down2(val[ls(at)], tag[at]); down2(val[rs(at)], tag[at]);
        down2(tag[ls(at)], tag[at]); down2(tag[rs(at)], tag[at]);
        tag[at] = 1;
    }
}
void update(int nl, int nr, int k, int l = 1, int r = n, int at = 1)
{
    if(nl <= l && r <= nr) { return down2(val[at], k), down2(tag[at], k), void(0); } 
    push_down(at); int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, nr, k, l, mid, ls(at));
    if(nr > mid) update(nl, nr, k, mid + 1, r, rs(at));
}
void upSon(int u) { update(id[u], id[u] + sz[u] - 1, u); }
int query(int x, int l = 1, int r = n, int at = 1)
{
    if(l == r) return val[at];
    push_down(at); int mid = (l + r) >> 1;
    return (x <= mid) ? query(x, l, mid, ls(at)) : query(x, mid + 1, r, rs(at));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i = 1, u,v; i < n; i++) { cin >> u >> v; addEdge(u,v); addEdge(v,u); }
    for(int i = 1; i <= (n << 2); i++) val[i] = tag[i] = 1;
    dfs(1,0,1); dfs(1,1);
    while(Q--)
    {
        char op; int u; cin >> op >> u;
        if(op == 'C') upSon(u); else cout << query(id[u]) << '\n';
    }
    return 0;
}