祥符网站建设,上海房地产网站官网,免费个人简历制作网站,上海法律网站建设题干#xff1a;
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一棵N的节点的树#xff0c;节点编号1~N#xff0c;并且1号节点是根节点。
小Hi会反复询问小Ho一个问题#xff1a;给定两个节点a和b#xff0c;有多少对节点c和d满足c d且c到d的…题干
时间限制: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
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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;
vectorint vv[MAX];
void dfs(int cur,int rt) {dep[cur] dep[rt]1;sum[cur] 1;for(int i 1; i31; i) {fa[cur][i] fa[fa[cur][i-1]][i-1];}int sz vv[cur].size();for(int i 0; isz; 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; i31; i) {if(dci 1) u fa[u][i];}if(u v) {return ans1;}else return ans2;for(int i 31; i0 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()
{cinnm;for(int u,v,i 1; in-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;cinuv;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; i0; i--) {//if(dci 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; i0 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; i0; i--) {//if(dci 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; i0 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; i0 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代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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;
vectorint vv[MAX];
void dfs(int cur,int rt) {dep[cur] dep[rt]1;sum[cur] 1;for(int i 1; i31; i) {fa[cur][i] fa[fa[cur][i-1]][i-1];}int sz vv[cur].size();for(int i 0; isz; 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; i0 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()
{cinnm;for(int u,v,i 1; in-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);//cinuv;cout lca(u,v) endl;}return 0 ;}总结 另外注意一下对于一棵树dep值大的是在下面啊远离根别想反了。
