欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HNOI 2016 树

程序员文章站 2024-03-02 23:04:40
...

解读题意

1.有n个点的模板树
2.每次把模板树上a为根的子树接到大树的b下面
3.求两个点在大树上的距离

切分

P30暴力模拟:
1.全部连边
2.求lca

正解流程

1.对于那么多个接子树操作,显然不能全部接到大树上,那么试着接点别的代替
2.只把子树的根接到大树上
3.为了能求距离,接上去的边权应为两个结点在大树上的距离
4.对于序号的映射,就是在模板树上求区间第K值

具体操作

1.预处理模板树的主席树
2.建边(用主席树找到(大树)b点在模板树上的序号,(大树)b点对应的(大树的)结点序号,求出的dis+1就是新边权),新结点编号是总点数+1。
3.大树点的序号=大树上对应结点编号-1+模板树上第K大
4.对于每个询问,如果在同一结点上,直接映射到模板树上求lca;不在一个结点上,先求出其到(大树)结点的距离,在求大树上两个结点的距离

代码如下

#include<bits/stdc++.h>
using namespace std;
const int M=500005;
int n,m,Q;
int TD[M],To[M];
long long ID[M];
vector<int>E[M];
int head[M],asdf;
struct edge {
    int to,nxt,cost;
} G[M*2];
void add_edge(int a,int b,int c) {
    G[++asdf].to=b;
    G[asdf].nxt=head[a];
    G[asdf].cost=c;
    head[a]=asdf;
}
int tot,Ls[M*20],Rs[M*20],sum[M*20],root[M];
void build(int &rt,int L,int R) {
    rt=++tot;
    sum[rt]=0;
    if(L==R)return;
    int mid=L+R>>1;
    build(Ls[rt],L,mid);
    build(Rs[rt],mid+1,R);
}
void update(int &rt,int pr,int x,int L,int R) {
    rt=++tot;
    sum[rt]=sum[pr]+1;
    Ls[rt]=Ls[pr],Rs[rt]=Rs[pr];
    if(L==R)return;
    int mid=L+R>>1;
    if(x<=mid)update(Ls[rt],Ls[pr],x,L,mid);
    else update(Rs[rt],Rs[pr],x,mid+1,R);
}
int query(int rt,int pr,int K,int L,int R) {
    if(L==R)return L;
    int mid=L+R>>1;
    if(sum[Ls[rt]]-sum[Ls[pr]]>=K)return query(Ls[rt],Ls[pr],K,L,mid);
    else return query(Rs[rt],Rs[pr],K-sum[Ls[rt]]+sum[Ls[pr]],mid+1,R);
}
int fa[M][20],DEP[M];
long long dis[M];
int par[M][20],dfn[M],dep[M],dR[M],tid[M],siz[M];
void dfsI(int x,int f) {
    siz[x]=1;
    dfn[x]=++tot;
    par[x][0]=f;
    dep[x]=dep[f]+1;
    tid[tot]=x;
    for(int i=0; i<E[x].size(); i++) {
        int y=E[x][i];
        if(y==f)continue;
        dfsI(y,x);
        siz[x]+=siz[y];
    }
    dR[x]=tot;
}
void dfsII(int x,int f) {
    fa[x][0]=f;
    DEP[x]=DEP[f]+1;
    for(int i=head[x]; i; i=G[i].nxt) {
        int y=G[i].to;
        if(y==f)continue;
        dis[y]=dis[x]+G[i].cost;
        dfsII(y,x);
    }
}
int lca(int a,int b) {
    if(dep[a]>dep[b])swap(a,b);
    int tmp=dep[b]-dep[a];
    for(int i=0; i<20; i++) {
        if(tmp&1)b=par[b][i];
        tmp>>=1;
    }
    if(a==b)return a;
    for(int i=19; i>=0; i--) {
        if(par[a][i]!=par[b][i]) {
            a=par[a][i];
            b=par[b][i];
        }
    }
    return par[a][0];
}
int Dep(int a,int b) {
    return dep[a]+dep[b]-2*dep[lca(a,b)];
}
int LCA(int a,int b) {
    if(DEP[a]>DEP[b])swap(a,b);
    int tmp=DEP[b]-DEP[a];
    for(int i=0; i<20; i++) {
        if(tmp&1)b=fa[b][i];
        tmp>>=1;
    }
    if(a==b)return a;
    for(int i=19; i>=0; i--) {
        if(fa[a][i]!=fa[b][i]) {
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
long long Dis(int a,int b) {
    return dis[a]+dis[b]-2*dis[LCA(a,b)];
}
int find(int a,int b) {
    int tmp=DEP[a]-DEP[b]-1;
    for(int i=0; i<20; i++) {
        if(tmp&1)a=fa[a][i];
        tmp>>=1;
    }
    return a;
}
int main() {
    scanf("%d %d %d",&n,&m,&Q);
    int a,b;
    for(int i=1; i<n; i++) {
        scanf("%d %d",&a,&b);
        E[a].push_back(b);
        E[b].push_back(a);
    }
    //小树倍增
    dfsI(1,0);
    for(int i=1; i<20; i++) {
        for(int j=1; j<=n; j++) {
            par[j][i]=par[par[j][i-1]][i-1];
        }
    }
    tot=0;
    build(root[0],1,n);
    for(int i=1; i<=n; i++) {
        update(root[i],root[i-1],tid[i],1,n);
    }
    ID[1]=TD[1]=To[1]=1;
    for(int i=1; i<=m; i++) {
        long long b;
        scanf("%d %lld",&a,&b);
        int t=upper_bound(ID+1,ID+i+1,b)-ID-1;
        b=query(root[dR[TD[t]]],root[dfn[TD[t]]-1],b-ID[t]+1,1,n);
        int dd=Dep(TD[t],b);
        add_edge(t,i+1,dd+1);
        add_edge(i+1,t,dd+1);
        To[i+1]=b;
        ID[i+1]=ID[i]+siz[TD[i]];
        TD[i+1]=a;
    }
    dfsII(1,0);
    for(int i=1; i<20; i++) {
        for(int j=1; j<=m+1; j++) {
            fa[j][i]=fa[fa[j][i-1]][i-1];
        }
    }
    for(int i=1; i<=Q; i++) {
        long long a,b;
        scanf("%lld %lld",&a,&b);
        int t1=upper_bound(ID+1,ID+m+2,a)-ID-1;
        int t2=upper_bound(ID+1,ID+m+2,b)-ID-1;
        int x=query(root[dR[TD[t1]]],root[dfn[TD[t1]]-1],a-ID[t1]+1,1,n);
        int y=query(root[dR[TD[t2]]],root[dfn[TD[t2]]-1],b-ID[t2]+1,1,n);
        if(t1==t2) {
            printf("%d\n",Dep(x,y));
        } else {
            int c=LCA(t1,t2);
            long long ans=dis[t1]+dis[t2]-2*dis[c];
            ans+=Dep(TD[t1],x);
            ans+=Dep(TD[t2],y);
            int xx,yy;
            if(t1==c)xx=x;
            else xx=To[find(t1,c)];
            if(t2==c)yy=y;
            else yy=To[find(t2,c)];
            ans-=2*Dep(lca(xx,yy),TD[c]);
            printf("%lld\n",ans);
        }
    }
    return 0;
}
相关标签: 区间第K值 lca