2018 Multi-University Training Contest 7 - Tree

梦里梦外; 2022-01-07 05:21 171阅读 0赞

# LCT + 树上倍增 #

和bzoj的弹飞绵羊差不多，多了一个倍增记录父亲节点。

这里有个小技巧，把飞出去的点当成第1个比较好操作。。不像弹飞绵羊是第n+1个，因为这里是往上跳，所以出去了的话我们的父亲节点就是0，直接把节点+1当初LCT中的点就好了

#include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    #define full(a, b) memset(a, b, sizeof a)
    #define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
    using namespace std;
    typedef long long ll;
    inline int lowbit(int x){ return x & (-x); }
    inline int read(){
        int X = 0, w = 0; char ch = 0;
        while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
        while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
        return w ? -X : X;
    }
    inline int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }
    inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
    template<typename T>
    inline T max(T x, T y, T z){ return max(max(x, y), z); }
    template<typename T>
    inline T min(T x, T y, T z){ return min(min(x, y), z); }
    template<typename A, typename B, typename C>
    inline A fpow(A x, B p, C lyd){
        A ans = 1;
        for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
        return ans;
    }
    const int N = 100005;
    int _, n, m, t, tot, ch[N][2], size[N], rev[N], fa[N], p[N][21], st[N], to[N];
    
    void build(){
        ++ tot;
        size[tot] = 1, fa[tot] = ch[tot][0] = ch[tot][1] = rev[tot] = 0;
    }
    
    bool isRoot(int x){
        return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
    }
    
    void push_up(int x){
        size[x] = size[ch[x][0]] + size[ch[x][1]] + 1;
    }
    
    void reverse(int x){
        rev[x] ^= 1;
        swap(ch[x][0], ch[x][1]);
    }
    
    void push_down(int x){
        if(rev[x]){
            if(ch[x][0]) reverse(ch[x][0]);
            if(ch[x][1]) reverse(ch[x][1]);
            rev[x] ^= 1;
        }
    }
    
    void rotate(int x){
        int y = fa[x], z = fa[y], p = (ch[y][1] == x) ^ 1;
        ch[y][p^1] = ch[x][p], fa[ch[x][p]] = y;
        if(!isRoot(y)) ch[z][ch[z][1] == y] = x;
        fa[x] = z, fa[y] = x, ch[x][p] = y;
        push_up(y), push_up(x);
    }
    
    void splay(int x){
        int pos = 0; st[++ pos] = x;
        for(int i = x; !isRoot(i); i = fa[i]) st[++ pos] = fa[i];
        while(pos) push_down(st[pos --]);
        while(!isRoot(x)){
            int y = fa[x], z = fa[y];
            if(!isRoot(y)){
                (ch[y][0] == x) ^ (ch[z][0] == y) ? rotate(x) : rotate(y);
            }
            rotate(x);
        }
        push_up(x);
    }
    
    void access(int x){
        for(int p = 0; x; p = x, x = fa[x])
            splay(x), ch[x][1] = p, push_up(x);
    }
    
    void makeRoot(int x){
        access(x), splay(x), reverse(x);
    }
    
    void split(int x, int y){
        makeRoot(x), access(y), splay(y);
    }
    
    void link(int x, int y){
        makeRoot(x);
        fa[x] = y;
    }
    
    void cut(int x, int y){
        split(x, y);
        fa[x] = ch[y][0] = 0;
        push_up(y);
    }
    
    int find(int x, int k){
        int u = x;
        for(int i = 0; k; k >>= 1, i ++)
            if(k & 1) u = p[u][i];
        return u;
    }
    
    int main(){
    
        for(_ = read(); _; _ --){
            tot = 0, full(to, 0);
            n = read();
            t = (int)(log(n) / log(2)) + 1;
            for(int i = 2; i <= n; i ++){
                p[i][0] = read();
            }
            for(int i = 1; i <= t; i ++){
                for(int j = 1; j <= n; j ++){
                    p[j][i] = p[p[j][i - 1]][i - 1];
                }
            }
            for(int i = 1; i <= n + 1; i ++) build();
            for(int i = 1; i <= n; i ++){
                to[i] = find(i, read());
                link(i + 1, to[i] + 1);
            }
            m = read();
            while(m --){
                int opt = read();
                if(opt == 1){
                    int u = read();
                    split(1, u + 1);
                    printf("%d\n", size[u + 1] - 1);
                }
                else{
                    int u = read(), k = read();
                    cut(u + 1, to[u] + 1);
                    to[u] = find(u, k);
                    link(u + 1, to[u] + 1);
                }
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/onionQAQ/p/10952034.html