Codeforces Round #482 (Div. 2) ：C

题目连接：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

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 3e5+100;
 5 
 6 vector <int> ve[maxn];
 7 int n,x,y;
 8 int vis[maxn];
 9 void init(){
10     memset(vis,-1, sizeof(vis));
11     scanf("%d%d%d",&n,&x,&y);
12     for(int i=1;i<n;i++){
13         int a,b;
14         scanf("%d%d",&a,&b);
15         ve[a].push_back(b);
16         ve[b].push_back(a);
17     }
18 }
19 
20 int find(int pos){
21     vis[pos] = -2;
22     if(pos == y) {
23         vis[y] = 0;
24         return 0;
25     }
26     for(int i=0;i<ve[pos].size();i++) {
27         int v = ve[pos][i];
28         if(vis[v] == -1) {
29             if(find(v) == 0) {
30                 vis[pos] = 0;
31                 return 0;
32             }
33         }
34     }
35     return vis[pos];
36 }
37 
38 ll cnt_chx;
39 void find_chx(int pos){
40     vis[pos] = 1;
41     cnt_chx++;
42     for(int i=0;i<ve[pos].size();i++) {
43         int v = ve[pos][i];
44         if(vis[v] < 0)
45             find_chx(v);
46     }
47 }
48 
49 ll cnt_chy;
50 void find_chy(int pos) {
51     vis[pos] = 2;
52     cnt_chy++;
53     for(int i=0;i<ve[pos].size();i++) {
54         int v = ve[pos][i];
55         if(vis[v] < 0)
56             find_chy(v);
57     }
58 }
59 
60 int main(){
61     init();
62     ll ans = (ll)n*((ll)n-(ll)1);
63     find(x);
64     find_chx(x);
65     find_chy(y);
66     ans -= cnt_chx*cnt_chy;
67     printf("%lld
",ans);
68     return 0;
69 }