毛毛虫

[题目链接](https://www.nowcoder.com/practice/02b12ffe5e374b85bfa7e708abfb038a)

思路

在以 1 为根的有根树上，两只毛毛虫分别从节点 $a$ 和 $b$ 出发，只能往更深的方向走，走到叶子节点停下。问所有可能到达的 $(p_1, p_2)$ 二元组个数。

关键观察

毛毛虫从节点 $u$ 出发，能到达的叶子节点恰好就是 $u$ 的子树中所有的叶子。因此每次询问的答案就是：

$ $\text{ans}(a, b) = \text{leafCnt}(a) \times \text{leafCnt}(b)$ $

其中 $\text{leafCnt}(u)$ 表示节点 $u$ 的子树中叶子节点的数量。如果 $u$ 本身就是叶子（无子节点），则 $\text{leafCnt}(u) = 1$ 。

预处理

由于输入已经按编号顺序给出了每个节点的父亲（ $f_2, f_3, \ldots, f_n$ ），且保证 $f_i < i$ ，所以我们可以直接按编号从大到小累加：

初始化所有叶子节点的 $\text{leafCnt} = 1$ （叶子就是没有子节点的节点）。
从编号 $n$ 到 $2$ ，将 $\text{leafCnt}(i)$ 累加到 $\text{leafCnt}(f_i)$ 上。

这样无需建图，也无需 DFS， $O(n)$ 即可完成预处理。

回答询问

读入所有 $a_i$ 和 $b_i$ ，对每个询问计算 $\text{leafCnt}(a_i) \times \text{leafCnt}(b_i)$ ，全部异或起来输出即可。

样例验证

树结构：1 的子节点为 2、3；2 的子节点为 4、5；3 的子节点为 6、7、8。

$\text{leafCnt}$ ：节点 4-8 各为 1，节点 2 为 2，节点 3 为 3，节点 1 为 5。
查询 (4,5)： $1 \times 1 = 1$ ；(2,3)： $2 \times 3 = 6$ ；(1,2)： $5 \times 2 = 10$ ；(5,8)： $1 \times 1 = 1$ 。
$1 \oplus 6 \oplus 10 \oplus 1 = 12$ ，与样例输出一致。

复杂度

时间复杂度： $O(n + Q)$ ，预处理 $O(n)$ ，回答询问 $O(Q)$ 。
空间复杂度： $O(n + Q)$ 。

代码

C++
Java

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, Q;
    cin >> n >> Q;

    vector<int> fa(n + 1);
    vector<long long> leaf(n + 1, 0);
    vector<bool> hasChild(n + 1, false);

    for(int i = 2; i <= n; i++){
        cin >> fa[i];
        hasChild[fa[i]] = true;
    }

    // 叶子节点 leafCnt = 1，然后从大到小累加到父节点
    for(int i = 1; i <= n; i++){
        if(!hasChild[i]) leaf[i] = 1;
    }
    for(int i = n; i >= 2; i--){
        leaf[fa[i]] += leaf[i];
    }

    vector<int> a(Q), b(Q);
    for(int i = 0; i < Q; i++) cin >> a[i];
    for(int i = 0; i < Q; i++) cin >> b[i];

    long long ans = 0;
    for(int i = 0; i < Q; i++){
        ans ^= leaf[a[i]] * leaf[b[i]];
    }
    cout << ans << "\n";
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);

        st.nextToken(); int n = (int) st.nval;
        st.nextToken(); int Q = (int) st.nval;

        int[] fa = new int[n + 1];
        long[] leaf = new long[n + 1];
        boolean[] hasChild = new boolean[n + 1];

        for (int i = 2; i <= n; i++) {
            st.nextToken();
            fa[i] = (int) st.nval;
            hasChild[fa[i]] = true;
        }

        for (int i = 1; i <= n; i++) {
            if (!hasChild[i]) leaf[i] = 1;
        }
        for (int i = n; i >= 2; i--) {
            leaf[fa[i]] += leaf[i];
        }

        int[] a = new int[Q], b = new int[Q];
        for (int i = 0; i < Q; i++) {
            st.nextToken();
            a[i] = (int) st.nval;
        }
        for (int i = 0; i < Q; i++) {
            st.nextToken();
            b[i] = (int) st.nval;
        }

        long ans = 0;
        for (int i = 0; i < Q; i++) {
            ans ^= leaf[a[i]] * leaf[b[i]];
        }
        System.out.println(ans);
    }
}