Codeforces Round #482 (Div. 2) ：C - Kuro and Walking Route

题目连接：http://codeforces.com/contest/979/problem/C

解题心得：

题意就是给你n个点，在点集中间有n-1条边（无重边），在行走的时候不能从x点走到y点，问你任意两点一共有多少种走法，u到v和v到u为不同的走法。
首先要明白的是n个点n-1条边就是一棵树。而在树中任意两点有且仅有一条路径。这样就简单了，先从x点dfs到y点，将唯一的一条路径标记上就将树x点和y点形成的子树分开了。然后不走标记的点就可以再次dfs的得到x点子树上的点数sumx，以及y点子树上的点数sumy。答案就是n*(n-1)-sumx*sumy

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 3e5+;

 vector <int> ve[maxn];

 int n,x,y;

 int vis[maxn];

 void init(){

     memset(vis,-, sizeof(vis));

     scanf("%d%d%d",&n,&x,&y);

     for(int i=;i<n;i++){

         int a,b;

         scanf("%d%d",&a,&b);

         ve[a].push_back(b);

         ve[b].push_back(a);

     }

 }

 int find(int pos){

     vis[pos] = -;

     if(pos == y) {

         vis[y] = ;

         return ;

     }

     for(int i=;i<ve[pos].size();i++) {

         int v = ve[pos][i];

         if(vis[v] == -) {

             if(find(v) == ) {

                 vis[pos] = ;

                 return ;

             }

         }

     }

     return vis[pos];

 }

 ll cnt_chx;

 void find_chx(int pos){

     vis[pos] = ;

     cnt_chx++;

     for(int i=;i<ve[pos].size();i++) {

         int v = ve[pos][i];

         if(vis[v] < )

             find_chx(v);

     }

 }

 ll cnt_chy;

 void find_chy(int pos) {

     vis[pos] = ;

     cnt_chy++;

     for(int i=;i<ve[pos].size();i++) {

         int v = ve[pos][i];

         if(vis[v] < )

             find_chy(v);

     }

 }

 int main(){

     init();

     ll ans = (ll)n*((ll)n-(ll));

     find(x);

     find_chx(x);

     find_chy(y);

     ans -= cnt_chx*cnt_chy;

     printf("%lld\n",ans);

     return ;

 }

巴特西

Codeforces Round #482 (Div. 2) ：C - Kuro and Walking Route

最新文章

热门文章