社区讨论
求条
P14260 期待(counting)参与者 3已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mhj04gga
- 此快照首次捕获于
- 2025/11/03 18:32 4 个月前
- 此快照最后确认于
- 2025/11/03 18:32 4 个月前
做的是n^2的做法,求条(无需改进复杂的)
CPP// T4-counting.cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
using ll = long long;
using PII = pair<int, int>;
const int MAXN = 1e5 + 100;
vector<int> G[MAXN], vec1, vec2;
int disS[MAXN], disY[MAXN], n, s, y;
void dfs(int u, int fa, int dis[]) {
for(const int v : G[u]) {
if(v == fa) continue;
dis[v] = dis[u] + 1;
dfs(v, u, dis);
}
}
void dfsS(int u, int fa, bool flag) {
if(u == y) flag = 1;
if(flag) vec1.push_back(u);
for(const int v : G[u]) {
if(v == fa) continue;
dfsS(v, u, flag);
}
}
void dfsY(int u, int fa, bool flag) {
if(u == s) flag = 1;
if(flag) vec2.push_back(u);
for(const int v : G[u]) {
if(v == fa) continue;
dfsY(v, u, flag);
}
}
inline void solve() {
cin >> n >> s >> y;
vec1.clear(), vec2.clear();
for(int i = 0; i <= n; i ++) G[i].clear();
for(int u, v, i = 1; i < n; i ++) {
cin >> u >> v;
G[u].push_back(v), G[v].push_back(u);
}
disS[s] = disY[y] = 0;
dfs(s, 0, disS), dfs(y, 0, disY);
dfsS(s, 0, 0), dfsY(y, 0, 0);
int ANS = 0;
// cerr << "len" << vec1.size() << " " << vec2.size() << "\n";
for(int i : vec1) for(int j : vec2) {
int a = disY[i], c = disS[j], b = disS[y];
ANS += 2 * (a + b + c - max({a, c})) - b + 1;
}
cout << ANS << "\n";
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
// freopen("counting.in", "r", stdin);
// freopen("counting.out", "w", stdout);
int T = 1;
cin >> T;
while(T --) solve();
return 0;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...