题解：CF979C Kuro and Walking Route

Luo_Yicheng · 2025-08-27 15:37:56 · 题解

题意

Kuro 想要在一棵树上选择两个不同的节点 u 和 v 作为步行路线的起点和终点。但是，他避免选择那些路径上先经过节点 x 再经过节点 y 的 (u,v) 对。需要计算所有满足条件的 (u, v) 对的数量。

分析

算法

图的遍历。

数据结构

数组，STL vector（邻接表存图）。

过程分析

观察到 1\le n\le3\times10^5，考虑 O(n) 做法，即每个节点只遍历一次。

步骤：存图，DFS 两次计算 x,y 节点的子树大小。

详细解法

1. 输入 + 存图

   cin >> n >> x >> y;
   for (int i = 1; i < n; i++){
   int a, b;
   cin >> a >> b;
   g[a].push_back(b);
   g[b].push_back(a); //双向存图
   }

2. 我们知道这棵树共有 n\times(n-1) 个 (u,v) 对。且不难发现，若 u 是 x 节点的子树，且 v 是 y 节点的子树，那么 u 到 v 的路径就一定不合规。我们可以以 y 为根节点，遍历这棵树到达 x 结束，则 n 减去遍历过的节点数量，就是 x 的子树大小。求 y 用一样的思路。这样我们就可以得出，若 x 的子树大小为 sx，y 为 sy，不合规的点对数量为 sx\times sy，答案则为 n\times(n-1)-sx\times sy。

   shouldnot = y; //不能走到的节点
   dfs(x, x); //从 x 开始遍历
   int ans = n - sum; //记录子树大小
   sum = 0;
   shouldnot = x; //重置
   dfs(y, y);
   ans *= (n - sum);
   cout << (n - 1) * n - ans;

3. DFS 内部。

   void dfs(int u, int f){ //当前节点和父节点
   if (u == shouldnot)
       return; //如果走到 shouldnot 节点，结束 DFS。
   sum++; //累加遍历过的数量
   for (int i : g[u]){ //遍历所有能到达的节点
       if (i != f) //防止走会父节点
           dfs(i, u); //更新 u,f
   }
   }

   总结

   时间复杂度：O(n)。

空间复杂度：O(n)。

代码可通过：