题解 P7394 【「TOCO Round 1」History】

· · 题解

离线操作树 + bfs序 + 树状数组

首先发现这题要求退回到历史版本而未要求强制在线，而且对树的操作也是可逆的，所以可以把所有操作与询问按影响顺序连成一棵操作树。这样每个对每个询问有影响的操作是操作树上的一个前缀。于是我们只需要对操作树进行 dfs，进入节点时执行对应的操作，退出时则撤销操作。

然后考虑询问的特点，如果 y 为奇数时，答案显然为 0；若为偶数，则满足条件的节点一定是 x 的 \frac{y}{2} 级父亲的 \frac{y}{2} 级儿子，但需要注意的是，x 的 \frac{y}{2}-1 级父亲的 \frac{y}{2}-1 级儿子也满足前述条件但不满足询问条件，所以我们可以把一个询问拆成两个形如「x 的 k 级父亲的 k 级儿子上权值和」的问题。

然后可以发现一个性质，被拆解后的询问每次涉及的点是原树 bfs 序上连续的一段，具体证明也不难。

然后问题就被转化为了 bfs 序上单点修改区间求和问题，可以用常数小的树状数组解决。

考虑确定询问的区间，可以先把询问离线，用 [Cnoi2019]雪松果树 中的 dfs + 差分 的方法求出询问节点的 k 级父亲的 k 级儿子的数量，然后用被 dfs 到的时间差确定该节点在区间内的相对位置，从而确定询问的区间，这部分时间复杂度为 O(n+m)，具体可以参考下方的代码。

总时间复杂度 O(m\log n)，空间复杂度 O(n+m)。

参考代码(略丑勿喷) :

#include<bits/stdc++.h>
using namespace std;

const int N = 100000;

vector<int> to[200005];
int deep[200005];
int id  [200005];       // bfs 序
int stk [200005];
int bin [200005];

int que[200005][3];
int len[200005];        // 区间长度
int lef[200005];        // 时间差

vector<int> ct[200005];
vector<int> q1[200005];
vector<int> q2[200005];

int val[200005];
int ans[200005];

namespace BIT{
    int c[100005], N = 100004;
    int lowbit( int x ) { return x & -x; }
    void modify( int x, int v ) { for( ;x < N; x += lowbit(x) ) c[x] += v; } 
    int query( int x ) { int r = 0; for( ; x; x -= lowbit(x) ) r += c[x]; return r; }
}

void dfs1( int x, int f ) {
    deep[x] = deep[f] + 1; stk[ deep[x] ] = x;
    for( auto Q : q1[x] ) if( que[Q][2] < deep[x] ) 
      { q2[ stk[ deep[x] - que[Q][2] ] ].push_back(Q); }
    for( auto N : to[x] ) if( N ^ f ) dfs1( N, x );
}

void dfs2( int x, int f ) {
    for( auto Q : q2[x] ) len[Q] -= bin[ deep[x] + que[Q][2] ];
    bin[ deep[x] ] ++;
    for( auto Q : q1[x] ) lef[Q] = len[Q] + bin[ deep[x] ];
    for( auto N : to[x] ) if( N ^ f ) dfs2( N, x );
    for( auto Q : q2[x] ) len[Q] += bin[ deep[x] + que[Q][2] ];
}

void dfs3( int x ) {
    int y = que[x][1], z = N + x;
    if( que[x][0] == 1 ) BIT::modify( id[y], val[y] ? -1 : 1 ), val[y] ^= 1;
    if( que[x][0] == 2 ) if( len[x] )
      { ans[x] += BIT::query( id[y] - lef[x] + len[x] ) - BIT::query( id[y] - lef[x] );
        ans[x] -= BIT::query( id[y] - lef[z] + len[z] ) - BIT::query( id[y] - lef[z] ); }
    for( auto N : ct[x] ) dfs3(N);
    if( que[x][0] == 1 ) BIT::modify( id[y], val[y] ? -1 : 1 ), val[y] ^= 1;
}

void bfs() {
    queue<int> Q; Q.push(1);
    int cnt = 0;
    while( Q.size() ) {
        int x = Q.front(); Q.pop(); id[x] = ++ cnt;
        for( auto N : to[x] ) if( !id[N] ) Q.push(N);
    }
}

int main() {
    int n, m; cin >> n;
    for( int i = 1; i < n; i ++ )
      { int u, v; cin >> u >> v;
        to[u].push_back(v); 
        to[v].push_back(u); }
    cin >> m;
    for( int i = 1; i <= m; i ++ ) {
        cin >> que[i][0];
        if( que[i][0] == 1 or que[i][0] == 2 )
          { ct[i - 1].push_back(i); }
        if( que[i][0] == 1 ) cin >> que[i][1];
        if( que[i][0] == 2 ) cin >> que[i][1] >> que[i][2];
        if( que[i][0] == 3 ) 
          { int k; cin >> k; ct[k].push_back(i); }
        if( que[i][0] == 2 ) if( que[i][2] % 2 == 0 ) 
          { q1[ que[i][1] ].push_back(i); 
            q1[ que[i][1] ].push_back(i + N);
            que[i][2] /= 2;
            que[i + N][1] = que[i][1];
            que[i + N][2] = que[i][2] - 1; }
    }
    bfs(); dfs1( 1, 0 ); dfs2( 1, 0 ); dfs3(0);
    for( int i = 1; i <= m; i ++ ) if( que[i][0] == 2 ) cout << ans[i] << "\n";
}