E. Eert Esiwtib

Solution

由于值域很小，考虑对每个更新整棵树计算对应的询问。

设表示以为根的子树得到的三种答案分别是什么，容易发现i连的若干个子树的对答案的贡献互不影响，那么来看看如何转移：

• 如果当前点连到子节点的边是
  • 对于答案，有，所以可以直接
  • 对于答案，有，所以可以
  • 对于答案，就麻烦些，考虑对所有位分成两部分，一部分是包含的，一部分是不包含的，那么不包含的部分显然可以用直接转移，包含的部分就需要考虑一下子树大小的奇偶，如果是奇数则对应位全是1，否则全是0，所以有
• 如果当前点连到子节点的边是
  • 对于答案，有，所以有
  • 对于答案，有，所以有
  • 对于答案，，还是分成两部分，显然不为1的位在最后答案不可能是1，所以直接就是
• 如果当前点连到子节点的边是
  • 对于答案，有，显然为1的位要保证在所有的里面至少有一处使得这一位在和里不同，所以对于为1的位要求，对于为0的位要求，写成式子就是
  • 对于答案，有，对于为1的位在结果中为0的条件是在这个位是1，为1的位在结果中为的条件是在这个位是0，所以有
  • 对于答案，有，只用按异或次数的奇偶来转移即可，即

所以转移是的，总复杂度为。

另外，特别注意转移时不包含自身，要把自身的影响也算进去。

ll ans[N][3], tmp[N], a[N], dp[N][3];
int sz[N];
vector<pair<int, int> >q[105], to[N];
void dfs(int x) {
    sz[x] = 1;
    dp[x][1] = -1;
    dp[x][0] = dp[x][2] = 0;
    for (auto y : to[x]) {
        dfs(y.first);
        if (y.second == 0) {
            dp[x][0] |= a[x] | (dp[y.first][0] | a[y.first]);
            dp[x][1] &= a[x] | (dp[y.first][1] & a[y.first]);
            dp[x][2] ^= ((sz[y.first] & 1) ? a[x] : 0) | ((~a[x]) & (dp[y.first][2] ^ a[y.first]));
        }
        else if (y.second == 1) {
            dp[x][0] |= a[x] & (dp[y.first][0] | a[y.first]);
            dp[x][1] &= a[x] & (dp[y.first][1] & a[y.first]);
            dp[x][2] ^= a[x] & (dp[y.first][2] ^ a[y.first]);
        }
        else {
            dp[x][0] |= (a[x] & (~(dp[y.first][1] & a[y.first]))) | ((~a[x]) & (dp[y.first][0] | a[y.first]));
            dp[x][1] &= (a[x] & (~(dp[y.first][0] | a[y.first]))) | ((~a[x]) & (dp[y.first][1] & a[y.first]));
            dp[x][2] ^= ((sz[y.first] & 1) ? a[x] : 0) ^ (dp[y.first][2] ^ a[y.first]);
        }
        sz[x] += sz[y.first];
    }
}

int main() {
    int n = fast_IO::read(), Q = fast_IO::read();
    for (int i = 1; i <= n; ++i)tmp[i] = fast_IO::read();
    for (int i = 2; i <= n; ++i) {
        int fa = fast_IO::read(), opt = fast_IO::read();
        to[fa].push_back(make_pair(i, opt));
    }
    for (int i = 1; i <= Q; ++i) {
        int d = fast_IO::read(), x = fast_IO::read();
        q[d].push_back(make_pair(x, i));
    }
    for (int i = 0; i <= 100; ++i) {
        if (q[i].empty())continue;
        for (int j = 1; j <= n; ++j)a[j] = tmp[j] + i * j;
        dfs(1);
        for (auto j : q[i]) {
            ans[j.second][0] = dp[j.first][0];
            ans[j.second][1] = dp[j.first][1];
            ans[j.second][2] = dp[j.first][2];
        }
    }
    for (int i = 1; i <= Q; ++i)
        for (int j = 0; j < 3; ++j)
            printf("%lld%c", ans[i][j], j == 2 ? '\n' : ' ');
    return 0;
}