标签：掉落 Apple int Tree Codeforces 苹果 ans 节点
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;
}
标签：掉落,
Apple,
int,
Tree,
Codeforces,
苹果,
ans,
节点
From： https://www.cnblogs.com/Trilliverse/p/17607713.html