题意:给定一棵以 1 为根的有根树,每个点给定一个能量 x 表示这个点能将石头丢到该点的第 val 个父亲, 现在有两种操作,第一种询问在点 u 放一个石头需要多少次才能将石头丢至树外,第二种操作修改一个点 ux 值。
做法:先通过倍增预处理每个点的第 2^i 的父亲是谁,且将点 0 作为 1 的父亲并表示丢到树外面的点。然后建一棵 LCT0 的点权 val 置为 0 ,其他点权均置为 1 ,然后将每个点和跳一次能到的祖先连边,询问的答案就变成了 0u 路径上的 \sum val

#include <bits/stdc++.h>
#include <ext/rope>

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define X first
#define Y second
#define scd(a) scanf("%d", &a)
#define scdd(a,b) scanf("%d%d", &a, &b)
#define scddd(a,b,c) scanf("%d%d%d", &a, &b,&c)
#define mset(var,val) memset(var, val, sizeof(var))
#define MP make_pair
#define PB push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-9;

template <class T>
void test(T t){
    cout<<t<<"\n";
}
template <class T, class T2>
void test(T t, T2 t2){
    cout<<t<<" "<<t2<<"\n";
}
template <class T, class T2, class T3>
void test(T t, T2 t2, T3 t3){
    cout<<t<<" "<<t2<<" "<<t3<<"\n";
}

const int N = 2e5+10;

struct Node *null;
struct Node{
    Node *fa, *ch[2];
    int sum, val;
    int rev;
    inline void clear(int _val){
        fa = ch[0] = ch[1] = null;
        val = sum = _val;
        rev = 0;
    }
    inline void push_up(){
        sum = val + ch[0]->sum + ch[1]->sum;
    }
    inline void setc(Node *p, int d){
        ch[d] = p;
        p->fa = this;
    }
    inline bool d(){
        return fa->ch[1] == this;
    }
    inline bool isroot(){
        return fa == null || fa->ch[0] != this && fa->ch[1] != this;
    }
    inline void flip(){
        if(this == null) return;
        swap(ch[0], ch[1]);
        rev ^= 1;
    }
    inline void rot(){
        Node *f = fa, *ff = fa->fa;
        int c = d(), cc = fa->d();
        f -> setc(ch[!c], c);
        this -> setc(f, !c);
        if(ff->ch[cc] == f) ff->setc(this, cc);
        else this->fa = ff;
        f->push_up();
    }
    inline Node* splay(){
        while(!isroot()){
            if(!fa->isroot())
                d() == fa->d() ? fa->rot() : rot();
            rot();
        }
        push_up();
        return this;
    }
    inline Node* access(){
        for(Node *p = this, *q = null; p != null; q = p, p = p->fa){
            p->splay()->setc(q,1);
            p->push_up();
        }
        return splay();
    }
    inline Node* find_root(){
        Node *x;
        for(x = access(); x->ch[0] != null; x = x->ch[0]);
        return x;
    }
    void make_root(){
        access()->flip();
    }
    void cut(){
        access();
        ch[0]->fa = null;
        ch[0] = null;
        push_up();
    }
    void cut(Node *x){
        x -> make_root();
        cut();
    }
    void link(Node *x){
        make_root();fa = x;
    }
};

Node pool[N], *tail;
Node *node[N];

int ask(Node *x, Node *y){
    x->access();
    for(x = null; y != null; x = y, y = y->fa){
        y->splay();
        if(y->fa == null)
            return y->val + y->ch[1]->sum + x->sum;
        y->setc(x, 1);
        y->push_up();
    }
}

int fa[N][22];

void work(){
    int n;
    scd(n);
    for(int i = 2; i <= n; ++i){
        scd(fa[i][0]);
    }
    for(int j = 1; j < 20; ++j){
        for(int i = 1; i <= n; ++i){
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
    tail = pool;
    null = tail++;
    null->clear(0);
    node[0] = tail++;
    node[0]->clear(0);
    rep1(i,n){
        node[i] = tail++;
        node[i]->clear(1);
    }
    rep1(i,n){
        int x;
        scd(x);
        int u = i;
        rep(j,20){
            if((1<<j) & x){
                u = fa[u][j];
            }
        }
        node[i]->link(node[u]);
    }
    int q;
    scd(q);
    for(;q--;){
        int op;
        scd(op);
        if(op == 1){
            int x;
            scd(x);
            printf("%d\n", ask(node[0], node[x]));
        }
        else{
            int x, y;
            scdd(x, y);
            node[x]->cut(node[0]);
            int u = x;
            rep(j,20){
                if((1<<j) & y){
                    u = fa[u][j];
                }
            }
            node[x]->link(node[u]);
        }
    }
}


int main(int argc, const char * argv[]) {
    // IOS;
    int t;
    scd(t);
    for(;t--;)
        work();
    return 0;
}
分类: 未分类

发表评论

电子邮件地址不会被公开。 必填项已用*标注

隐藏
变装