题解：CF979C Kuro and Walking Route

题意

Kuro 想要在一棵树上选择两个不同的节点

u

和

v

作为步行路线的起点和终点。但是，他避免选择那些路径上先经过节点

x

再经过节点

y

的

(u,v)

对。需要计算所有满足条件的

(u, v)

对的数量。

分析

算法

图的遍历。

数据结构

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

过程分析

观察到

1\le n\le3\times10^5

，考虑

O(n)

做法，即每个节点只遍历一次。

步骤：存图，DFS 两次计算

x,y

节点的子树大小。

详细解法

输入 + 存图

CPP

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); //双向存图
}

我们知道这棵树共有 $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$ 。

CPP

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;

DFS 内部。

CPP

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)

。

代码可通过：

题解：CF979C Kuro and Walking Route

文章操作

题意

分析

算法

数据结构

过程分析

详细解法

总结

相关推荐

评论

题解：CF979C Kuro and Walking Route