題干：

時間限制:10000ms

單點時限:1000ms

內存限制:256MB

描述

給定一棵N的節點的樹，節點編號1~N，并且1號節點是根節點。 ?

小Hi會反復詢問小Ho一個問題：給定兩個節點a和b，有多少對節點c和d滿足c < d且c到d的路徑包含完整的a到b的路徑？

你能幫幫小Ho嗎？

輸入

第一行包含兩個數N和M，依次是節點總數和問題總數。 ?

第2~N行每行包含兩個整數u和v，代表u是v的父節點。 ?

以下M行每行包含兩個整數a和b，代表一個問題。

對于30%的數據，1 ≤ N, M ≤ 1000

對于100%的數據，1 ≤ N, M ≤ 100000

輸出

對于每個問題輸出一個整數，代表答案。

樣例輸入

7 2 1 2 1 3 2 4 2 5 3 6 3 7 2 3 2 4

樣例輸出

9 6

解題報告：

? 跑半遍LCA，到他倆深度相同的時候停止。然后判斷是否在同一條鏈上，分別返回不同的答案就行了。注意在同一條鏈的時候，不能用u和v的，需要用u(深度大的)的和對應鏈上dep[v]+1的那個點的。（來看幾發錯誤代碼）

錯誤代碼1：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; ll a[MAX]; int fa[MAX][33],dep[MAX],sum[MAX]; int n,m; vector<int> vv[MAX]; void dfs(int cur,int rt) {dep[cur] = dep[rt]+1;sum[cur] = 1;for(int i = 1; i<=31; i++) {fa[cur][i] = fa[fa[cur][i-1]][i-1];}int sz = vv[cur].size();for(int i = 0; i<sz; i++) {int v = vv[cur][i];if(v == rt) continue;dfs(v,cur);sum[cur] += sum[v];} } int lca(int u,int v) {if(dep[u] < dep[v]) swap(u,v);ll ans1 = 1LL*sum[u] * (n - sum[v] + (sum[v]-sum[u]));ll ans2 = 1LL*sum[u] * sum[v];int dc = dep[u] - dep[v];for(int i = 0; i<=31; i++) {if(dc>>i & 1) u = fa[u][i];}if(u == v) {return ans1;}else return ans2;for(int i = 31; i>=0 && u != v ; i--) {if(fa[u][i] != fa[v][i]) {u = fa[u][i];v = fa[v][i];}}int res = fa[u][0];//u和v的最近公共祖先.} int main() {cin>>n>>m;for(int u,v,i = 1; i<=n-1; i++) {scanf("%d%d",&u,&v);fa[v][0] = u;vv[u].pb(v);vv[v].pb(u);}dfs(1,0);while(m--) {int u,v;cin>>u>>v;cout << lca(u,v) <<endl;}return 0 ;}

錯誤代碼2：

ll lca(int u,int v) {if(dep[u] < dep[v]) swap(u,v);//ll ans1 = (n - sum[v] + (sum[v]-sum[u]));ll sumu = sum[u] ,sumv = sum[v];int dc = dep[u] - dep[v];for(int i = 31; i>=0; i--) {//if(dc>>i & 1) u = fa[u][i];if(dep[u]-1 != dep[v]) {u = fa[u][i];} }if(fa[u][0] == v) {//說明在一條鏈上 return sumu*(n-sum[u]);}else return sumu*sumv;for(int i = 31; i>=0 && u != v ; i--) {if(fa[u][i] != fa[v][i]) {u = fa[u][i];v = fa[v][i];}}int res = fa[u][0];//u和v的最近公共祖先. }

錯誤代碼3：

ll lca(int u,int v) {if(dep[u] < dep[v]) swap(u,v);//ll ans1 = (n - sum[v] + (sum[v]-sum[u]));ll sumu = sum[u] ,sumv = sum[v];int dc = dep[u] - dep[v];for(int i = 31; i>=0; i--) {//if(dc>>i & 1) u = fa[u][i];if(dep[u] < dep[v]) {u = fa[u][i];} }if(fa[u][0] == v) {//說明在一條鏈上 return sumu*(n-sum[u]);}else return sumu*sumv;for(int i = 31; i>=0 && u != v ; i--) {if(fa[u][i] != fa[v][i]) {u = fa[u][i];v = fa[v][i];}}int res = fa[u][0];//u和v的最近公共祖先. }

錯誤代碼4：

ll lca(int u,int v) {if(dep[u] < dep[v]) swap(u,v);ll sumu = sum[u] ,sumv = sum[v];for(int i = 31; i>=0 && dep[v] + 1 <= dep[u]; i--) {if(dep[fa[u][i]] < dep[v]) {u = fa[u][i];} }if(fa[u][0] == v) {//說明在一條鏈上 return sumu*(n-sum[u]);}else return sumu*sumv; }

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; ll a[MAX]; int fa[MAX][33],dep[MAX],sum[MAX]; int n,m; vector<int> vv[MAX]; void dfs(int cur,int rt) {dep[cur] = dep[rt]+1;sum[cur] = 1;for(int i = 1; i<=31; i++) {fa[cur][i] = fa[fa[cur][i-1]][i-1];}int sz = vv[cur].size();for(int i = 0; i<sz; i++) {int v = vv[cur][i];if(v == rt) continue;dfs(v,cur);sum[cur] += sum[v];} } ll lca(int u,int v) {if(dep[u] < dep[v]) swap(u,v);ll sumu = sum[u] ,sumv = sum[v];for(int i = 31; i>=0 && dep[v] + 1 <= dep[u]; i--) {if(dep[fa[u][i]] < dep[v]) {u = fa[u][i];} }if(fa[u][0] == v) {//說明在一條鏈上 return sumu*(n-sum[u]);}else return sumu*sumv; } int main() {cin>>n>>m;for(int u,v,i = 1; i<=n-1; i++) {scanf("%d%d",&u,&v);fa[v][0] = u;vv[u].pb(v);vv[v].pb(u);}dfs(1,0);while(m--) {int u,v;scanf("%d%d",&u,&v);//cin>>u>>v;cout << lca(u,v) <<endl;}return 0 ;}

總結：

? 另外注意一下，，，對于一棵樹，dep值大的是在下面啊（遠離根），別想反了。

總結

以上是生活随笔為你收集整理的【hihocoder - offer编程练习赛60 C】路径包含问题（LCA，树上倍增）的全部內容，希望文章能夠幫你解決所遇到的問題。

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