＂中国东信杯＂广西大学第二届程序设计竞赛（同步赛)G.Antinomy与LaHee大森林

https://ac.nowcoder.com/acm/contest/2908/G

思路：显然地，对于n个点而言，总共可以走的路径数为n*(n-1)
对于所求地就有可走路径=总路径数-不可走路径数
那么问题就转化成了如何计算不可走地路径数
可以这样考虑
对于节点a而言，他的子树的节点如果要走出这颗子树外，那么一定要经过点a
所以我们可以把x当作树根，算出y的子树大小，然后再以y当树根，算出x的子树大小
那么不可走路径数即为两数相乘 （子树大小：以该节点为父节点下的节点个数）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
vector<int> g[400005];
int s[400005];
int n,x,y;
void dfs(int x,int f){

       s[x]=1;
       for(auto it:g[x]){
          if(it!=f){
             dfs(it,x);
             s[x]+=s[it];
          }
       }
}
int main()
{
     ///freopen("1.in","r",stdin);
     ///freopen("1.out","w",stdout);
     cin>>n>>x>>y;
     rep(i,0,n-1){
        int a,b;
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
     }
     dfs(x,0);
     int k=s[y];
     me(s,0);
     dfs(y,0);
     cout<<1ll*n*(n-1)-1ll*k*s[x]<<endl;
   
   return 0;
}