题意分析

题目要求我们处理一棵有根树，并回答多个查询，每个查询给出两个节点u和v，要求找到它们的最近公共祖先（LCA）。最后统计每个节点作为LCA出现的次数，并按节点编号升序输出。

解题思路

1. 树的表示：首先需要表示这棵树。可以使用邻接表的方式存储，同时记录每个节点的父节点和深度信息。由于树是有根的，我们需要找到根节点（根节点是没有父节点的节点）。

2. LCA算法：对于每对查询(u, v)，我们需要找到它们的LCA。常用的算法有：

   • 暴力法：将u和v的路径上的所有祖先记录下来，然后找它们的公共祖先中深度最大的。这种方法在树较深时效率较低。
   • 倍增法：预处理每个节点的2^k级祖先，然后通过二进制提升快速找到LCA。这种方法预处理时间O(nlogn)，每次查询O(logn)。
   • Tarjan离线算法：可以离线处理所有查询，但实现较为复杂。
   • 欧拉序+RMQ：将树转换为欧拉序，然后通过RMQ（区间最小值查询）来找到LCA。

   由于节点数n≤900，暴力法在本题中也是可行的，但为了效率，可以选择倍增法。

3. 统计次数：对于每个查询的结果，统计每个节点作为LCA出现的次数。

具体步骤

1. 输入处理：
   • 读取节点数n。
   • 读取每个节点的子节点信息，构建邻接表，并记录每个节点的父节点（子节点的父节点指向当前节点）。
   • 找到根节点（没有父节点的节点）。
2. 预处理：
   • 使用BFS或DFS计算每个节点的深度。
   • 对于倍增法，预处理每个节点的2^k级祖先。
3. 处理查询：
   • 对于每对(u, v)，使用倍增法找到它们的LCA。
   • 统计LCA出现的次数。
4. 输出结果：
   • 按节点编号升序输出每个节点及其作为LCA的次数。

代码实现

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 910;

vector<int> tree[MAXN];
int parent[MAXN];
int depth[MAXN];
int ancestor[MAXN][10]; // 2^10 = 1024 > 900
int lcaCount[MAXN];

void dfs(int u, int p) {
    parent[u] = p;
    depth[u] = depth[p] + 1;
    ancestor[u][0] = p;
    for (int i = 1; i < 10; ++i) {
        ancestor[u][i] = ancestor[ancestor[u][i-1]][i-1];
    }
    for (size_t i = 0; i < tree[u].size(); ++i) {
        int v = tree[u][i];
        if (v != p) {
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = 9; i >= 0; --i) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = ancestor[u][i];
        }
    }
    if (u == v) return u;
    for (int i = 9; i >= 0; --i) {
        if (ancestor[u][i] != ancestor[v][i]) {
            u = ancestor[u][i];
            v = ancestor[v][i];
        }
    }
    return parent[u];
}

int main() {
    int n;
    while (cin >> n) {
        // Initialize
        for (int i = 0; i <= n; ++i) {
            tree[i].clear();
        }
        memset(parent, 0, sizeof(parent));
        memset(depth, 0, sizeof(depth));
        memset(ancestor, 0, sizeof(ancestor));
        memset(lcaCount, 0, sizeof(lcaCount));

        // Read tree
        int root = -1;
        for (int i = 0; i < n; ++i) {
            int u, cnt;
            char c;
            cin >> u >> c >> c >> cnt >> c;
            for (int j = 0; j < cnt; ++j) {
                int v;
                cin >> v;
                tree[u].push_back(v);
                tree[v].push_back(u);
            }
            if (root == -1) root = u;
        }

        // Preprocess
        depth[0] = -1;
        dfs(root, 0);

        // Read queries
        int m;
        cin >> m;
        for (int i = 0; i < m; ++i) {
            int u, v;
            char c;
            cin >> c >> u >> v >> c;
            int a = lca(u, v);
            lcaCount[a]++;
        }

        // Output results
        for (int i = 1; i <= n; ++i) {
            if (lcaCount[i] > 0) {
                cout << i << ":" << lcaCount[i] << endl;
            }
        }
    }
    return 0;
}