2024河南省萌新联赛第四场I
2024 河南省萌新联赛第四场 I \huge{2024河南省萌新联赛第四场I} 2024河南省萌新联赛第四场I
文章目录
- 题意
- 思路
- 标程
题目地址：I-马拉松_河南萌新联赛2024第（四）场：河南理工大学 (nowcoder.com)
题意
给出一棵树，要求求出经过特定两个节点的路径个数。
思路
如图所示，我们令其中一个节点作为root节点，那么所有经过这两个节点的路径条数即为：图中红蓝两个区域的节点个数乘积。
标程
#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long const int mod = 1e9 + 7;
const int N = 3e5 + 10;int n, cx, cy;
vector<vector<int>> v(N);
vector<int> a(N);
vector<bool> b(N, false);void dfs(int x, int y, bool z) {if(z) b[x] = true;a[x] ++;for(auto i : v[x]) {if(i == y) continue;if(i == cy) dfs(i, x, true);else dfs(i, x, z);a[x] += a[i];if(b[i]) b[x] = true;}
}void Solved() {cin >> n >> cx >> cy;for(int i = 1; i < n; i ++ ) {int x, y; cin >> x >> y;v[x].push_back(y); v[y].push_back(x);}dfs(cx, cx, false);int sum = 1;for(auto i : v[cx]) {if(!b[i]) sum += a[i];}cout << sum * a[cy] << endl;
}signed main(void) {IOSint ALL = 1;while(ALL -- ) Solved();return 0;
}