?

Kuro is living in a country called Uberland, consisting of?nn?towns, numbered from?11to?nn, and?n?1n?1?bidirectional roads connecting these towns. It is possible to reach each town from any other. Each road connects two towns?aa?and?bb. Kuro loves walking and he is planning to take a walking marathon, in which he will choose a pair of towns?(u,v)(u,v)?(u≠vu≠v) and walk from?uu?using the shortest path to?vv?(note that?(u,v)(u,v)?is considered to be different from?(v,u)(v,u)).

Oddly, there are 2 special towns in Uberland named Flowrisa (denoted with the index?xx) and Beetopia (denoted with the index?yy). Flowrisa is a town where there are many strong-scent flowers, and Beetopia is another town where many bees live. In particular, Kuro will avoid any pair of towns?(u,v)(u,v)?if on the path from?uu?to?vv, he reaches Beetopia after he reached Flowrisa, since the bees will be attracted with the flower smell on Kuro’s body and sting him.

Kuro wants to know how many pair of city?(u,v)(u,v)?he can take as his route. Since he’s not really bright, he asked you to help him with this problem.

Input

The first line contains three integers?nn,?xx?and?yy?(1≤n≤3?1051≤n≤3?105,?1≤x,y≤n1≤x,y≤n,?x≠yx≠y) - the number of towns, index of the town Flowrisa and index of the town Beetopia, respectively.

n?1n?1?lines follow, each line contains two integers?aa?and?bb?(1≤a,b≤n1≤a,b≤n,?a≠ba≠b), describes a road connecting two towns?aa?and?bb.

It is guaranteed that from each town, we can reach every other town in the city using the given roads. That is, the given map of towns and roads is a tree.

Output

A single integer resembles the number of pair of towns?(u,v)(u,v)?that Kuro can use as his walking route.

Examples

Input 3 1 3
1 2
2 3 Output 5 Input 3 1 3
1 2
1 3 Output 4

Note

On the first example, Kuro can choose these pairs:

• (1,2)(1,2): his route would be?1→21→2,
• (2,3)(2,3): his route would be?2→32→3,
• (3,2)(3,2): his route would be?3→23→2,
• (2,1)(2,1): his route would be?2→12→1,
• (3,1)(3,1): his route would be?3→2→13→2→1.

Kuro can't choose pair?(1,3)(1,3)?since his walking route would be?1→2→31→2→3, in which Kuro visits town?11?(Flowrisa) and then visits town?33?(Beetopia), which is not allowed (note that pair?(3,1)(3,1)?is still allowed because although Kuro visited Flowrisa and Beetopia, he did not visit them in that order).

On the second example, Kuro can choose the following pairs:

• (1,2)(1,2): his route would be?1→21→2,
• (2,1)(2,1): his route would be?2→12→1,
• (3,2)(3,2): his route would be?3→1→23→1→2,
• (3,1)(3,1): his route would be?3→13→1.

?

題意：

給你一個含有N 個節點的樹，

并且有兩個節點比較特殊分別是x和y，

特殊之處是不能有一個路徑是先走過x后又走過y。因為那樣咱們題目的主公人會被蜜蜂叮咬。

求還剩多少個簡單路徑可以走？

思路：

一個圖上所以簡單路徑的個數是 n*(n-1) .

而不能走的路徑是先走過x后又走過y。

我們想一下會有哪些簡單路徑是先經過x后經過y。

我們看圖，我畫的一個不好看的樹，

如果1是x，3是y，那么1和它左邊連著的幾個節點不能去3以及3右邊的幾個節點。

那么我們只需要由x節點在樹上dfs時遇到y節點不繼續搜，那么沒訪問到的節點的個數就是x不能去訪問的y和y的幾個節點。

反過來用y節點去dfs，可以得到x和x的那幾個節點計數為numx吧，

那么numx*numy就是我們不能走的簡單路徑，總路徑數減去不能走的就是我們要的答案數。

?

細節見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define rt return #define dll(x) scanf("%I64d",&x) #define xll(x) printf("%I64d\n",x) #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define db(x) cout<<"== [ "<<x<<" ] =="<<endl; using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;} inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ int n; std::vector<int> son[maxn]; int vis1[maxn]; int vis2[maxn]; int bid; int fid; void dfs1(int id,int pre) {vis1[id]=1;for(auto x:son[id]){if(x!=pre&&x!=fid){dfs1(x,id);}} } void dfs2(int id,int pre) {vis2[id]=1;for(auto x:son[id]){if(x!=pre&&x!=bid){dfs2(x,id);} } } int main() {//freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);//freopen("D:\\common_text\\code_stream\\out.txt","w",stdout); gbtb;cin>>n>>fid>>bid;int a,b;repd(i,2,n){cin>>a>>b;son[a].pb(b);son[b].pb(a);}dfs1(bid,-1);dfs2(fid,-1);ll num1=0ll;ll num2=0ll;repd(i,1,n){if(!vis1[i]){num1++;}if(!vis2[i]){num2++;}}ll ans=1ll*n*(n-1ll);ans-=num1*num2;cout<<ans<<endl;return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

?

轉載于:https://www.cnblogs.com/qieqiemin/p/10704950.html

總結

以上是生活随笔為你收集整理的Kuro and Walking Route CodeForces - 979C （树上DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。