【洛谷 P4116】 Qtree3 （树链剖分）

题目链接

树剖练手题，想复习下树剖。

第一次提交\(T\)成QQC

看我

???

看了数据范围的确挺恶心的，我的复杂度是\(O(Mlog^2N)\)的，数据范围有三段

For 1/3 of the test cases, N=5000, Q=400000.

For 1/3 of the test cases, N=10000, Q=300000.

For 1/3 of the test cases, N=100000, Q=100000.

很极限就对了。难道是我常数太大了？那也不至于只对\(3\)个点吧。

我看了一下，原来我求\(size\)的时候没有加上子树的\(size\)...这样就会剖出假的重链。

我加上去，再交，还是\(T\)成QQC。

看我

......

原来是标记\(top\)的时候错了。改过来就\(A\)了。

虽然有两个细节错误，但是没有别的错误，也就是说我树剖大致模板和线段树都是一次写对的。。

话不多说。

树剖后用线段树来维护，维护最小值，黑点的值为\(dfs\)序，白点的值为\(INF\)，每次查询找到链上的最小值即为答案。

因为从\(1\)到\(x\)是一条直链，越上的点也就是越靠近\(1\)的点，\(dfs\)序一定最小。

#include <cstdio>

#define INF 2147483647

#define re register

int s; char ch;

inline int read(){

    s = 0; ch = getchar();

    while(ch < '0' || ch > '9') ch = getchar();

    while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }

    return s;

}

inline int min(int a, int b){

    return a > b ? b : a;

}

const int MAXN = 100010;

struct Edge{

    int next, to;

}e[MAXN << 1];

int head[MAXN], num, n, m, a, b, w[MAXN];

inline void Add(int from, int to){

    e[++num].to = to; e[num].next = head[from]; head[from] = num;

    e[++num].to = from; e[num].next = head[to]; head[to] = num;

}

int dep[MAXN], size[MAXN], maxson[MAXN], top[MAXN], ID, dfn[MAXN], pos[MAXN], f[MAXN];

namespace SegTree{

    #define left (now << 1)

    #define right (now << 1 | 1)

    int Min[MAXN << 2];

    inline void pushup(int now){

        Min[now] = min(Min[left], Min[right]);

    }

    void build(int now, int l, int r){

        if(l == r){ Min[now] = INF; return; }

        int mid = (l + r) >> 1;

        build(left, l, mid);

        build(right, mid + 1, r);

        pushup(now);

    }

    void update(int now, int l, int r, int x){

        if(l == r){ Min[now] = (w[pos[x]] ? x : INF); return; }

        int mid = (l + r) >> 1;

        if(x <= mid) update(left, l, mid, x);

        else update(right, mid + 1, r, x);

        pushup(now);

    }

    int query(int now, int l, int r, int wl, int wr){

        if(l > wr || r < wl) return INF;

        if(l >= wl && r <= wr) return Min[now];

        int ans = INF, mid = (l + r) >> 1;

        ans = min(ans, query(left, l, mid, wl, wr));

        ans = min(ans, query(right, mid + 1, r, wl, wr));

        return ans;

    }

}using namespace SegTree;

void dfs1(int u, int fa){

    size[u] = 1; f[u] = fa;

    for(re int i = head[u]; i; i = e[i].next)

       if(e[i].to != fa){

         dfs1(e[i].to, u);

         size[u] += size[e[i].to];

         if(size[e[i].to] > size[maxson[u]])

           maxson[u] = e[i].to;

       }

}

void dfs2(int u, int rt){

    dfn[u] = ++ID; pos[ID] = u; top[u] = rt;

    if(maxson[u]) dfs2(maxson[u], rt);

    for(re int i = head[u]; i; i = e[i].next)

       if(e[i].to != f[u] && e[i].to != maxson[u])

         dfs2(e[i].to, e[i].to);

}

inline int solve(int u){

    int ans = INF;

    while(top[u] != 1){

      ans = min(ans, query(1, 1, n, dfn[top[u]], dfn[u]));

      u = f[top[u]];

    }

    ans = min(ans, query(1, 1, n, dfn[1], dfn[u]));

    return ans == INF ? -1 : pos[ans];

}

int main(){

    n = read(); m = read();

    for(re int i = 1; i < n; ++i)

       Add(read(), read());

    dfs1(1, 0);

    dfs2(1, 1);

    build(1, 1, n);

    for(re int i = 1; i <= m; ++i){

       a = read(); b = read();

       if(!a){

         w[b] ^= 1;

         update(1, 1, n, dfn[b]);

       }

       else printf("%d\n", solve(b));

    }

    return 0;

}

巴特西

【洛谷 P4116】 Qtree3 （树链剖分）

最新文章

热门文章