Codeforces 1843D：Apple Tree

Trilliverse / 2023-08-05 / 原文

1843D.Apple Tree

Description:

一棵树( \(Tree\) 无环无重边 ) \(n\) 个节点，根节点为1（节点编号 \(1\)~\(n\)），树上只有2个苹果，每次摇动苹果树时，每个苹果会有如下变化：
当前苹果位于节点 \(u\) :
1.若节点 \(u\) 有子节点，则该苹果移动到此节点（若有多个子节点，则可以到任意一个）。
2.若节点 \(u\) 没有字节点，则苹果掉落。
很显然，有限次操作后，两个苹果都会掉落。
\(q\) 次提问，每次给出两个苹果的节点位置 \(x\) 和 \(y\) ，求解组合\((a,b)\)的数量，其中节点 \(a\) 为苹果 \(x\) 掉落的位置，节点 \(b\) 为苹果 \(y\) 掉落的位置。

Analysis:

很显然，两个苹果为独立事件，苹果 \(x\) 的掉落可能位置数 \(ans\_x\)和相应的 \(ans\_y\)，则总 \(pairs=ans\_x \times ans\_y\)
\(dfs\) 即可，注意答案的累加

Solution:

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int maxn = 2e5+5;
 
vector<int> G[maxn];
ll ans[maxn];
int n;
 
void Build() { // 建树
	for(int i=1;i<=n;i++) {
		G[i].clear();
		ans[i] = 0;
	}
	cin >> n;
	for(int i=0;i<n-1;i++) {
		int u,v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
}
 
void dfs(int v, int pre) {
	if(G[v].size() == 1 && G[v][0] == pre) { // 掉落位置
		ans[v] = 1;
		return;
	}
	
	for(auto nxt : G[v]) {
		if(nxt == pre) continue; // 不要往父节点走
		dfs(nxt,v);
		ans[v] += ans[nxt]; //遍历点v的所有子节点，累加到v上
	}
}
 
void solve() {
	int q; cin >> q;
	while(q--) {
		int x,y; cin >> x >> y;
		ll sum = ans[x]*ans[y];
		cout << sum << endl;
	}
}
 
int main() {
	int t; cin >> t;
	while(t--) {
		Build();
		dfs(1,-1);
		solve();
	}
	return 0;
}