526互联

Codeforces Round 881 (Div. 3) D - Apple Tree（dfs）

发布时间 2023-07-15 10:59:40作者: 高尔赛凡尔娟

https://codeforces.com/contest/1843/problem/D

题目大意：

一颗树中，每次给定两个结点，每个结点都可以移动到孩子结点，最后可以到达叶子结点，

问我们这两个结点最终移到叶子结点有多少种组合？

（其实就是让求以这两个节点为根的子树的叶子结点个数的乘积）

input 
2
5
1 2
3 4
5 3
3 2
4
3 4
5 1
4 4
1 3
3
1 2
1 3
3
1 1
2 3
3 1
output 
2
2
1
4
4
1
2


input
2
5
5 1
1 2
2 3
4 3
2
5 5
5 1
5
3 2
5 3
2 1
4 2
3
4 3
2 1
4 2
output
1
2
1
4
2

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=200200,M=2023;
vector<LL> g[N];
LL cnt[N],maxn=0;
void dfs(LL idx,LL father)
{
    if(g[idx].size()==1&&g[idx][0]==father) cnt[idx]=1;
    else
    {
        for(int i=0;i<g[idx].size();i++)
        {
            if(g[idx][i]!=father)
            {
                dfs(g[idx][i],idx);
                cnt[idx]+=cnt[g[idx][i]];
            }
        }
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        memset(cnt,0,sizeof cnt);
        for(int i=0;i<=n;i++)
        {
            g[i].clear();
        }
        maxn=0;
        for(int i=1;i<n;i++)
        {
            LL u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1,-1);
        LL q;
        cin>>q;
        while(q--)
        {
            LL u,v;
            cin>>u>>v;
            cout<<cnt[u]*cnt[v]<<endl;
        }
    }
    return 0;
}