比赛 2024暑假C班集训E 评测结果 WWWWWWWWWWWWWWWWWWWWWWWWWWWWWAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
题目名称 部落冲突 最终得分 30
用户昵称 darkMoon 运行时间 6.705 s
代码语言 C++ 内存使用 16.28 MiB
提交时间 2024-07-14 10:49:21
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
// #define fin cin
// #define fout cout
ifstream fin("lct.in");
ofstream fout("lct.out");
auto mread = [](){
    int x;
    fin >> x;
    return x;
};
const int N = 3e5 + 5;
int n = mread(), m = mread(), s[N], siz[N], top[N], son[N], dfn[N], d[N], idx, rnk[N], w[N], now, fa[N];
vector<int> v[N];
void add(int x, int k){
    while(x <= n){
        s[x] += k;
        x += x & -x;
    }
    return;
}
int query(int x){
    int ans = 0;
    while(x){
        ans += s[x];
        x -= x & -x;
    }
    return ans;
}
void dfs1(int x, int fa2){
    // printf("*** %d\n", x);
    siz[x] = 1;
    int ma = 0, p = 0;
    for(int y : v[x]){
        if(y == fa2){
            continue;
        }
        fa[y] = x;
        d[y] = d[x] + 1;
        dfs1(y, x);
        siz[x] += siz[y];
        if(siz[y] > ma){
            ma = siz[y], p = y;
        }
    }
    if(ma){
        son[x] = p;
    }
    return;
}
void dfs2(int x, int fa2){
    if(x != 1){
        dfn[x] = ++idx;
        rnk[idx] = x;
    }
    if(son[x]){
        top[son[x]] = top[x];
        dfs2(son[x], x);
    }
    for(int y : v[x]){
        if(y == fa2 || y == son[x]){
            continue;
        }
        top[y] = y;
        dfs2(y, x);
    }
    return;
}
int lca(int l, int r){
    if(d[l] < d[r]){
        swap(l, r);
    }
    while(top[l] != top[r]){
        if(d[top[l]] >= d[top[r]]){
            l = fa[top[l]];
        }
        else{
            r = fa[top[r]];
        }
    }
    if(d[l] <= d[r]){
        return l;
    }
    else{
        return r;
    }
}
int makeAns(int l, int r){
    int ans = 0;
    int mid = lca(l, r);
    // printf("--- %d %d %d\n", l, r, mid);
    if(mid != l){
        while(top[l] != top[mid]){
            ans += query(dfn[l]) - query(fa[dfn[top[l]]]);
            l = fa[top[l]];
        }
        ans += query(dfn[l]) - query(dfn[mid]);
        // printf("### %d %d %d %d\n", dfn[l], dfn[mid], query(dfn[l]), query(dfn[top[l]]));
    }
    if(mid != r){
        while(top[r] != top[mid]){
            ans += query(dfn[r]) - query(dfn[fa[top[r]]]);
            r = fa[top[r]];
        }
        ans += query(dfn[r]) - query(dfn[mid]);
        // printf("### %d %d %d %d\n", dfn[r], dfn[mid], query(dfn[r]), query(dfn[top[r]]));
    }
    return ans;
}
signed main(){
    for(int i = 1, x, y; i < n; i ++){
        x = mread(), y = mread();
        v[x].push_back(y);
        v[y].push_back(x);
    }
    top[1] = 1;
    d[1] = 1;
    dfs1(1, 0);
    // for(int i = 1; i <= n; i ++){
    //     printf("%d ", rnk[i]);
    // }
    dfs2(1, 0);
    // printf("\n");
    while(m --){
        char c;
        fin >> c;
        if(c == 'Q'){
            int p = mread(), q = mread();
            fout << (makeAns(p, q) == 0 ? "Yes" : "No") << "\n";
        }
        else if(c == 'C'){
            int p = mread(), q = mread();
            if(d[p] > d[q]){
                swap(p, q);
            }
            add(dfn[q], 1);
            // printf("*** %d\n", dfn[q]);
            w[++now] = dfn[q];
        }
        else{
            int x = mread();
            add(w[x], -1);
        }
    }
    return 0;
}