倍增大专题
[AHOI2008] 紧急集合 / 聚会 - 洛谷
题意：给定一棵树，多次查询费马点（bushi
费马点的含义是：到三个点的距离之和最小
Solution:考虑画图发现树上三点两两求lca，必然至少两个相同，然后我们只需要让费马点为另一个点就可以了，因为这一段路程只需要一个点走就最好了。
//考虑到让一个点走多的路程，两点走短路程
//首先对多种情况画图，可以知道树上三点两两求lca，必然至少两个相同
vector<int> e[N];
int fa[N],son[N],dep[N],siz[N];
int top[N];
void dfs1(int u,int f){ //搞fa,dep,son
fa[u]=f;siz[u]=1;dep[u]=dep[f]+1;
for(int v:e[u]){
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v])son[u]=v;
}
}
void dfs2(int u,int t){ //搞top
top[u]=t; //记录链头
if(!son[u]) return; //无重儿子
dfs2(son[u],t); //搜重儿子
for(int v:e[u]){
if(v==fa[u]||v==son[u])continue;
dfs2(v,v); //搜轻儿子
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
int dis(int u,int v){
int mid=lca(u,v);
return dep[u]+dep[v]-2*dep[mid];
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;
int c1=lca(x,y),c2=lca(x,z),c3=lca(y,z);
int c=c1^c2^c3;
int ans=dis(x,c)+dis(y,c)+dis(z,c);
cout<<c<<" "<<ans<<endl;
}
}
Codeforces Round 294 (Div. 2)E
题意：给定一棵树，多次查询。每次查询给出两点，求到两个点距离相等点的个数。
Solution：特殊情况，两个点重合，答案是n。再考虑无解情况，如果两个点的距离是奇数，则不存在这样的点，答案是0。最后考虑距离是偶数的点，不妨假设u深度大于v
- u与v高度不同，则找到中点，找到u的k-1级祖先，也就是中点的包含u的儿子的子树，记这个中点的儿子为son，以son为根的子树包含u。答案是sz[mid]-sz[u】
- u与v高度相等则两者lca上面的点可以对答案做贡献，考虑求出lca，求出son1,son表示lca的亲子节点，以son1为根的子树包含u，以son2为根的子树包含v。考虑答案是sz[lca]-sz[son1]-sz[son2] + n-sz[lca];
本题用倍增比较合适，可以对距离倍增快速利用get函数找到我们的k级祖先
struct edge{
int v,w;
};
//思考：要想知道一个数有几个二级制位，直接n=__lg(x)
//我们可以知道<n最近的2的次幂，9最大的是8，8虽然是2的3次方，但要遍历它的每一位
//需要3到0开始，也就是考虑到0的影响，我们可以正好满足偏移。
//2的3次方有四位，也就是__lg(x)就是我们需要的最高位，从它开始往低遍历
vector<edge>e[N];
const int len=__lg(N);
int dep[N];
int d[N];
int f[N][len+2];
int sz[N];
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
f[u][0]=fa;sz[u]=1;
for(int i=1;i<=len;i++)f[u][i]=f[f[u][i-1]][i-1];
//预处理倍增数组
for(auto [v,w]:e[u]){
if(v==fa)continue;
d[v]=d[u]+w;
dfs(v,u);
sz[u]+=sz[v];
}
}
int get(int x,int k) {//k级祖先
for(int i=len;i>=0;i--) if((k >> i) & 1) x = f[x][i];
return x;
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=len;i>=0;i--){
if(dep[f[x][i]]>=dep[y])x=f[x][i];
}
//跳到相同深度
if(x==y)return y;
//提提前判本身就是祖先关系
//cerr<<x<<" "<<y<<endl;
for(int i=len;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];y=f[y][i];
}
// cerr<<i<<" "<<x<<" "<<y<<endl;
}
//cerr<<x<<" "<<y<<endl;
//倍增一起向上跳，直到父亲就是答案
return f[x][0];
}
int dis(int u,int v){
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
//lca的子树和去掉两个分支，本题需要求未知点祖先，无法使用树链跑分
void solve(){
cin>>n;//cin>>m;
for(int i=1;i<=n-1;i++){
int u,v;cin>>u>>v;
e[u].push_back({v,1});
e[v].push_back({u,1});
}
dfs(1,0);
//for(int i=1;i<=n;i++)cerr<<sz[i]<<" ";
//cerr<<endl;
cin>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;int mid=lca(u,v);
// cerr<<mid<<endl;
if(dep[u]<dep[v])swap(u,v);
int ans=0;
if(u==v)ans=n;
else {
int dist=dis(u,v);
if(dist%2)ans=0;
else {
if(dep[u]==dep[v]){
int k=dep[u]-dep[mid]-1;
int s1=get(u,k),s2=get(v,k);
ans=n-sz[s1]-sz[s2];
}
else {
int k=dist/2-1;
int s1=get(u,k);int s2=get(u,k+1);
ans=sz[s2]-sz[s1];
}
}
}
cout<<ans<<endl;
}
}
Minimum spanning tree for each edge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Cut - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
校赛亚轴（板子复习
http://oj.daimayuan.top/problem/805最小瓶颈生成树
注意倍增到最后两边都还要再挑一条边
题目：给定一张 n 个点 m 条边的无向图，每条边有一个权值，定义瓶颈路权值为某一条从点 i 到 j 的路径上的最大权值，有 q个询问，每次询问给出两个点 (s,t)，求从 s 到 t 的最小瓶颈路权值
Sol：先求最小生成树。然后求两点路径的最大边权值
int a[N];
struct edge{
int v;
int w;
};
vector<edge>e[N];
const int len=__lg(N);
int dep[N];
//int d[N];
int f[N][len+2];//数组多开
int ans[N][len+2];
struct edges{
int u,v,w;
bool operator<(const edges &t)const
{return w < t.w;}
}ff[M];//结构体存边
struct DSU {
vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
void add(int u,int v,int w){
e[u].push_back({v,w});
}
int cnt=0,tmp=0;
bool kruskal(){//返回的是原图的连通性，最小生成树的答案并没有返回，注意自己处理。
sort(ff+1,ff+m+1);
DSU dsu(n+1);
int cnt=0;
for(int i=1; i<=m; i++){
int x=(ff[i].u);
int y=(ff[i].v);
if(!dsu.same(x,y))
{
dsu.merge(x,y);
add(ff[i].u,ff[i].v,ff[i].w);
add(ff[i].v,ff[i].u,ff[i].w);
tmp+=ff[i].w;
cnt++;
}
}
return cnt==n-1;
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
f[u][0]=fa;
for(int i=1;i<=len;i++){
f[u][i]=f[f[u][i-1]][i-1];
ans[u][i]=max(ans[u][i-1],ans[f[u][i-1]][i-1]);
//预处理倍增数组
}
for(auto [v,w]:e[u]){//加边权后增加参数w
if(v==fa)continue;
// d[v]=d[u]+w;
ans[v][0]=w;
dfs(v,u);
//sz[u]+=sz[v];
}
}
int lca(int x,int y){
int res=0;
if(dep[x]<dep[y])swap(x,y);
// cerr<<x<<" "<<y<<endl;
// bug(res);
for(int i=len;i>=0;i--){
if(dep[f[x][i]]>=dep[y]){res=max(res,ans[x][i]);x=f[x][i];}
}
//跳到相同深度
//cerr<<x<<endl;
if(x==y)return res;
//提提前判本身就是祖先关系
for(int i=len;i>=0;i--){
if(f[x][i]!=f[y][i]){
res=max(res,ans[x][i]);
res=max(res,ans[y][i]);
x=f[x][i];y=f[y][i];
}
}
//倍增一起向上跳，直到父亲就是答案
res=max(res,ans[y][0]);
return max(res,ans[x][0]);
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;cin>>u>>v>>w;
ff[i]={u,v,w};
}
kruskal();
// cerr<<tmp<<endl;
dfs(1,0);
// bug(ans[1][0]);
// bug(ans[2][0]);
int q;cin>>q;
for(int i=1;i<=q;i++){
int u,v;cin>>u>>v;
cout<<lca(u,v)<<endl;
}
}
https://www.luogu.com.cn/problem/CF1516D给你一个 \(n\) 个数的序列 \(a_i\)，和 \(q\) 次询问，每次询问一段区间 \([l,r]\)，问至少要把这个区间分为几个子区间，才能使得每个子区间内的数的乘积等于这个子区间内所有数的 \(LCM\) 。
\(n,a_i,q\le 10^5\)
Sol:先考虑固定L的情况，下一个端点在哪，由于lcm随集合大小单调性和质因数的限制我们可以得到。但最坏我们可能每次只能一步一步跳，所以我们倍增跳，在不超过的边界的情况下跳，最后再跳一步。
int a[N];
int f[N][21];
int v[N];
vector<int>c[N];
bool st[N];
void init(int mm){
for(int i=2;i<=mm;i++){
if(st[i])continue;
// bug(i);
c[i].push_back(i);
for(int j=i+i;j<=mm;j+=i){
st[j]=true;
c[j].push_back(i);
}
}
}
void solve(){
int q;
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
f[n+1][0]=n+1;
memset(v,0x3f,sizeof v);
for(int i=n;i>=1;i--){
f[i][0]=f[i+1][0];
for(auto j:c[a[i]]){
f[i][0]=min(f[i][0],v[j]);
v[j]=i;
}
}
for(int i=1;i<=20;i++){
for(int j=1;j<=n;j++){
if(f[j][i-1]<=n)f[j][i]=f[f[j][i-1]][i-1];
else f[j][i]=n+1;
}
}
while(q--){
int l,r;cin>>l>>r;
int ans=0;
for(int i=20;i>=0;i--){
if(f[l][i]<=r){
ans+=(1<<i);
l=f[l][i];
}
}
ans++;
cout<<ans<<endl;
}
}
对于边带权的有向图
标签：专题,res,int,siz,void,dep,lca,倍增 From： https://www.cnblogs.com/mathiter/p/18199391