题解 P4116 【Qtree3】

Treaker · 2019-10-06 05:51:35 · 题解

树链剖分

看见题解里有用set的，本人表示不是很会STL；

于是还是用是树剖+线段树过了这道题。。

我们发现一个事情就是，从1到v这条路径上的点的dfs序是越来越大，因为他的深度越来越大，所以我们可以通过这个性质来维护。。

我们对于黑点，让它的值等于它的dfs序，白点的话，直接赋inf，那么我查询的时候，只需要查询dfs序的最小值，再把它转化成编号即可。。

完整指针代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100005 , inf = 1e9;
inline int read()
{
    int x = 0 , f = 1;  char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')  f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
int n , Q , cnt;
int dfn[N] , size[N] , top[N] , fa[N] , dep[N] , hs[N] , id[N];
struct Tree_Div
{
    struct Edge
    {
        int to; Edge *nxt;
        Edge(int to,Edge *nxt) : to(to) , nxt(nxt) {}
    }*head[N];
    inline void add(int u,int v) {head[u] = new Edge(v,head[u]);}
    void get_tree(int x)
    {
        size[x] = 1;
        for(Edge *i = head[x];i;i = i -> nxt)
        {
            int to = i -> to;
            if(dep[to]) continue;
            dep[to] = dep[x] + 1;
            fa[to] = x;
            get_tree(to);
            size[x] += size[to];
            if(size[to] > size[hs[x]]) hs[x] = to;
        }
    }
    void dfs(int x,int topfa)
    {
        dfn[x] = ++cnt;
        id[cnt] = x;
        top[x] = topfa;
        if(hs[x]) dfs(hs[x],topfa);
        for(Edge *i = head[x];i;i = i -> nxt)
        {
            int to = i -> to;
            if(to == hs[x] || to == fa[x]) continue;
            dfs(to,to);
        }
    }
    #define mid ((p -> l + p -> r) >> 1)
    struct node
    {
        node *ls , *rs;
        int l , r , minn;
        node(int l,int r) : l(l) , r(r) {ls = rs = NULL; minn = inf;}
        inline void up() {minn = min(ls -> minn,rs -> minn);}
    }*root;
    void build(node *&p,int l,int r)
    {
        p = new node(l,r);
        if(l == r) return ;
        build(p -> ls,l,mid); build(p -> rs,mid+1,r); p -> up();
    }
    void chenge(node *p,int x)
    {
        if(p -> l == p -> r) return (void)(p -> minn == inf ? p -> minn = x : p -> minn = inf);
        x <= mid ? chenge(p -> ls,x) : chenge(p -> rs,x);
        p -> up();
    }
    int query(node *p,int x,int y)
    {
        if(x <= p -> l && p -> r <= y) return p -> minn;
        return min(x <= mid ? query(p -> ls,x,y) : inf,y > mid ? query(p -> rs,x,y) : inf);
    }
    inline int sec_query(int x)
    {
        int res = inf;
        while(top[x] != 1)
        {
            res = min(res,query(root,dfn[top[x]],dfn[x]));
            x = fa[top[x]];
        }
        res = min(res,query(root,dfn[1],dfn[x]));
        return res == inf ? -1 : id[res];
    }
    inline void LOL()
    {
        n = read(); Q = read();
        for(int i = 1 , u , v;i < n;i ++)
        {
            u = read(); v = read();
            add(u,v); add(v,u);
        } dep[1] = 1;
        get_tree(1);
        dfs(1,1);
        build(root,1,n);
        for(int i = 1 , opt , x;i <= Q;i ++)
        {
            opt = read(); x = read();
            if(opt & 1) printf("%d\n",sec_query(x));
            else chenge(root,dfn[x]);
        }
    }
}CF;
int main()
{
    CF.LOL();
    return 0;
}