建树小技巧1(树上路径问题)

题目链接:https://ac.nowcoder.com/acm/contest/2908/G

以 x 或者 y 结点作为根结点建树求解
用 x 结点建树作为例子：
先dfs标记每个结点的子节点个数，然后找到 y 的离 x 最近的父节点 z ，那么从 对应结点与 对应结点 的任意两点的最短路 必经过 x,y 结点 ，那么 即为不符合方案数。
那么答案即为： .

#include<bits/stdc++.h>
#define sscc ios::sync_with_stdio(false)
#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long ll;

const int maxn=4e5+10;



struct node{
    int to,next;
}edge[maxn<<1];

int tot,head[maxn];

void add( int u,int v )
{
    edge[tot]={v,head[u]};
    head[u]=tot++;
} 

void init()
{
    memset(head,-1,sizeof(head));
    tot=0;
}

ll siz[maxn],fa[maxn];

void dfs( int u,int f ) 
{
    fa[u]=f;
    siz[u]=1;
    for( int i=head[u];~i;i=edge[i].next )
    {
        int v=edge[i].to;
        if( v==f ) continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
} 

int main()
{
    sscc;
    cin.tie(0);cout.tie(0);
    int n,x,y;
    cin>>n>>x>>y;
    init();
    for( int i=1;i<n;i++ )
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(x,x);
    int k=y,num=siz[y];
    for( int i=y;;i=fa[i] )
    {
        num=siz[i];
        if( fa[i]==x ) break;
    }
    siz[x]-=num;
    cout<<(1ll*n*(n-1)-1ll*siz[x]*siz[y])<<endl;
    return 0;
}