社区讨论

求条

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 条回复,欢迎继续交流。

正在加载回复...