---

洛谷P5002 专心OI - 找祖先

---

标签

• LCA
• 树上统计
• 次方余项的计算

---

简明题意

• 给一颗有根树，再给m个询问，对于某个节点x，有多少对节点的LCA是x

---

思路

• 这题非常简单。我们假设要求x的答案。显然，LCA是x的一对节点，
  1. u，v != x，则u，v肯定位于x的不同两颗子树，那么答案显然就是$\sum 2\ast siz[u]\ast siz[v]$，其中siz[v]定义为子树v的大小。
  2. uv其中可能等于x的情况。这种情况下，uv其一是x，另一个可以是左右子树中的任意一个，那么答案显然就是siiz[u] * 2 - 1了。
• 求法：对于siz的大小，直接dfs就能得出了。那么对于1答案应该怎么求呢？难道要求出子树后，然后$o(n^2)$遍历吗?显然可以稍加优化，比如u有三棵子树，编号1，2，3。1中的答案应该是$2\ast siz[1]\ast siz[2]+2\ast siz[1]\ast siz[3]+2\ast siz[2]\ast siz[3]$，说到这里你想到了啥？这不就是$(siz[1]+siz[2]+siz[3]{)}^2-siz[1{]}^2-siz[2{]}^2-siz[3{]}^2$，然后就可以很容易的在递归中顺便处理掉

---

注意事项

• 题目指定了根，dfs时，不仅根时root，入口也应该是root，不要树剖做多了，就默认1是根或者入口

---

总结

• 有n个集合，每个集合里的元素个数是a[i]，现在问你从集合中选出两个元素有多少种选法？可以参照上面的方法，$元素总个{数}^2-\sum 每个集合元素个{数}^2$，如果是次方，也是类似的做法，我把他成为“次方余项的计算”

---

AC代码

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;int n, root, m;
vector<int> g[maxn];long long ans[maxn];int siz[maxn], fa[maxn];
void dfs1(int u, int f)
{fa[u] = f;siz[u] = 1;long long sum = 0;for (auto& v : g[u])if (v != f){dfs1(v, u);siz[u] += siz[v];sum -= siz[v] * siz[v];}ans[u] = sum + (siz[u] - 1) * (siz[u] - 1)  + siz[u] * 2 - 1;
}void solve()
{scanf("%d%d%d", &n, &root, &m);for (int i = 1; i < n; i++){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v), g[v].push_back(u);}dfs1(root, root);while (m--){int u;scanf("%d", &u);printf("%lld\n", ans[u] % mod);}
}int main()
{solve();return 0;
}

---

双倍经验

• 无