题目链接 题意:不能经过x之后再经过y,问有多少条路径满足题意 解析:一点到其他一点都只有一条道路,所以我们把从x到y的路径找出来之后,统计y之后的点数,记为cnt,把x之前的点数记为cnt3,之后令cnt++,cnt3++,也就是把x,y算上 令总点数减去不满足的路径数即可
#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<ll>G[N]; ll vis[N]; ll cnt,have,n,x,y,cnt1,cnt3,pp; void fi(ll a,ll pre) { vis[a]=1; //cout<<a<<' '<<pre<<endl; for(int i=0;i<G[a].size();i++) { ll b=G[a][i]; if(vis[b]) continue; if(pre) cnt++; if(b==y) fi(b,1); else fi(b,pre); } } void fi1(ll a) { if(pp) return ; vis[a]=1; //cout<<a<<endl; for(int i=0;i<G[a].size();i++) { ll b=G[a][i]; if(!vis[b]) { if(b==x) { pp=1; return ; } fi1(b); } } } void fi2(ll a) { vis[a]=1; for(int i=0;i<G[a].size();i++) { ll b=G[a][i]; if(!vis[b]) { cnt3++; fi2(b); } } } int main() { #ifdef LOCAL_DEFINE freopen("D:\\rush.txt","r",stdin); #endif ios::sync_with_stdio(false),cin.tie(0); cin>>n>>x>>y; pp=0; rep(i,0,n-2) { ll a,b; cin>>a>>b; G[a].pb(b); G[b].pb(a); } cnt=0,have=0,cnt1=0,cnt3=0; fi(x,0); memset(vis,0,sizeof vis); fi1(y); fi2(x); //cout<<cnt+1<<' '<<cnt3+1<<endl; cnt3++; cnt++; cout<<n*(n-1)-cnt3*(cnt)<<endl; return 0; }