企业网站管理系统 php,平邑建设局网站首页,郑州封控最新消息今天,网站建设的具体任务有哪些题目分析#xff1a;
这道题还是比较裸的一道书上差分的题目了 对于每一对标记点(x,y) 他们之间的路径就是 x − L C A ( x , y ) − y x-LCA(x,y)-y x−LCA(x,y)−y 这条路径上的每一条边都要经过。
那么对于一条边#xff0c;什么时候砍掉这条… 题目分析
这道题还是比较裸的一道书上差分的题目了 对于每一对标记点(x,y) 他们之间的路径就是 x − L C A ( x , y ) − y x-LCA(x,y)-y x−LCA(x,y)−y 这条路径上的每一条边都要经过。
那么对于一条边什么时候砍掉这条边的时候这几对点互相到达不了呢 那就是这条边是这m条路径一共m对点每一对点都有一条路径的公共边 也就是说这条边被经过了m次
因此对于每一条边我们用一个数组记录这条边被经过了几次 最后经过次数为m的边就是可以砍掉的边最后取一个max即可
那么我们如何累加边经过的次数呢 借鉴数列差分的思想我们利用树上差分去实现 对于一堆点 ( x , y ) (x,y) (x,y)我们令 s [ x ] , s [ y ] , s [ L c a ( x , y ) ] − 2 s[x],s[y],s[Lca(x,y)]-2 s[x],s[y],s[Lca(x,y)]−2 而后在树上做一遍前缀和即可 Code
#includebits/stdc.h
using namespace std;const int N 1e5100;int fa[N][30];
int n,m;
struct Node{int y,Next,id;
}e[2*N];
int len , Linkk[N];
int s[N];
int d[N];void Insert(int x,int y,int id){e[len] (Node){y,Linkk[x],id};Linkk[x] len;
}void Dfs(int x,int faa,int dd){d[x] dd;for (int i Linkk[x]; i; i e[i].Next){int y e[i].y;if (y faa) continue;fa[y][0] x;Dfs(y,x,dd1);}
}void Pre(){for (int j 1; (1 j) n; j)for (int i 1; i n; i)if (fa[i][j-1] -1) fa[i][j] -1;else fa[i][j] fa[fa[i][j-1]][j-1];
}int Lca(int x,int y){if (d[x] d[y]) swap(x,y);for (int i 0,dd d[y]-d[x];dd; dd1,i)if (dd1) y fa[y][i];if (x y) return x;for (int i 29; i 0; i--)if (fa[x][i] ! fa[y][i]) x fa[x][i] , y fa[y][i];return fa[x][0];
}void Plus(int x,int y){s[x] , s[y] , s[Lca(x,y)]-2;
}void Dfss(int x,int faa){for (int i Linkk[x]; i; i e[i].Next){int y e[i].y;if (y faa) continue;Dfss(y,x);s[x]s[y];}
}int Max -1;
void dfsM(int x,int faa){for (int i Linkk[x]; i; i e[i].Next){int y e[i].y; if (y faa) continue;if (s[y] m) Max max(Max,e[i].id);dfsM(y,x);}
}int main(){scanf(%d %d,n,m);for (int i 1,x,y; i n; i)scanf(%d %d,x,y) , Insert(x,y,i) , Insert(y,x,i);Dfs(1,0,0); fa[1][0] -1; Pre();for (int i 1 , x,y; i m; i)scanf(%d %d,x,y) , Plus(x,y);Dfss(1,0);dfsM(1,0);coutMax;return 0;
}
