【Codeforces Round #482 (Div. 2) C】Kuro and Walking Route

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

把x..y这条路径上的点标记一下。

然后从x开始dfs,要求不能走到那些标记过的点上。记录节点个数为cnt1(包括x)

然后从y开始dfs,也要求不能走到那些标记过的点上。记录节点个数为cnt2(包括y)

答案就为n(n-1)-cnt1cnt2;

(即所有的点对减去这些不符合要求的点对

【代码】

#include <bits/stdc++.h>

#define ll long long

#define pb push_back

#define inf 0x3f3f3f3f

#define pll pair<ll,ll>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define rep1(i,a,b) for(int i=a;i>=b;i--)

#define rson rt<<1|1,m+1,r

#define lson rt<<1,l,m

using namespace std;

const int N=3e5+100;

vector<int>G[N];

int vis[N];

int have,n,x,y;

int Pre[N+10];

int bo[N+10];

long long cnt[2];

void fx(int X,int pre){

    int len = G[X].size();

    for (int Y:G[X]){

        if (Y==pre) continue;

        Pre[Y] = X;

        fx(Y,X);

    }

}

void dfs(int X,int pre,int index){

    for (int Y:G[X]){

        if (bo[Y]) continue;

        if (Y==pre) continue;

        cnt[index]++;

        dfs(Y,X,index);

    }

}

//one more try?ok

int main()

{

    #ifdef LOCAL_DEFINE

        freopen("F:\\program\\rush\\rush_in.txt","r",stdin);

    #endif

    ios::sync_with_stdio(false),cin.tie(0);

    cin>>n>>x>>y;

    rep(i,0,n-2)

    {

        int a,b;

        cin>>a>>b;

        G[a].pb(b);

        G[b].pb(a);

    }

    fx(x,-1);

    for (int i = y; ;i = Pre[i]){

        bo[i] = true;

        if (i==x) break;

    }

    dfs(x,-1,0);

    dfs(y,-1,1);

    cnt[0]++;cnt[1]++;

    cout<<1LL*n*(n-1)-cnt[0]*cnt[1];

    return 0;

}