P10105 [GDKOI2023 提高组] 游戏

jr_linys · 2024-01-24 16:42:55 · 题解

P10105 [GDKOI2023 提高组] 游戏
去年Day2爆零打铜，今年又打铜。当时锯材务必的我赛后这题搞了两星期。

给出的 3 个距离对应的路径的交汇点为中心点，设中心点到那三个点的距离为 x,y,z。

可得

然后可用换根 DP 查找每个点的最长链、次长链、次次长链来自哪里，维护儿子方最长链、到根节点路径的倍增。

接着对一个询问，找到满足最长链、次长链的限制下次次长链最长的中心点，这是一个二维偏序问题。

#include<bits/stdc++.h>
using namespace std;
int read(){//哮哮快读
    char c;
    while(c=getchar(),c<'0'||c>'9');
    int x=c^'0';
    while(c=getchar(),c>='0'&&c<='9') x=x*10+(c^'0');
    return x;
}
const int N=2e5,M=18;
int n,logn,q,m,cnt;
int dep[N+5],siz[N+5][3],fr[N+5][3],zz[N+5][3];
int dss[N+5][2],ds[N+5][M],fa[N+5][M];
vector<int> g[N+5];

struct stu{int x,y,z,id;}dot[N+5],qs[N+5];
bool cmp(stu a,stu b){
    if(a.y==b.y) a.x>b.x;
    return a.y>b.y;
}
struct stu2{int x,id;}fuc[N+5];
bool cmp2(stu2 a,stu2 b){return a.x>b.x;}
int ans[N+5][3],xid[N+5];

void dfs1(int u,int fat){
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v!=fat){
            dep[v]=dep[u]+1;
            fa[v][0]=u;
            for(int i=1;i<=logn;i++) fa[v][i]=fa[fa[v][i-1]][i-1];//父节点方向倍增
            dfs1(v,u);

            for(int i=0;i<3;i++){
                if(siz[v][0]+1>siz[u][i]){
                    for(int j=2;j>i;j--) siz[u][j]=siz[u][j-1],fr[u][j]=fr[u][j-1],zz[u][j]=zz[u][j-1];
                    siz[u][i]=siz[v][0]+1,fr[u][i]=v,zz[u][i]=u;
                    break; 
                }
            }
        }
    }
    ds[u][0]=dss[u][0]=fr[u][0],dss[u][1]=fr[u][1];//重子链和次重子链方向
    for(int i=1;i<=logn;i++) ds[u][i]=ds[ds[u][i-1]][i-1];//重子链倍增
}
void dfs2(int u,int fat){
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v!=fat){
            int sizu,zzu;//换根，处理来自父节点方向的最长连
            if(fr[u][0]==v) sizu=siz[u][1]+1,zzu=zz[u][1];
            else sizu=siz[u][0]+1,zzu=zz[u][0];
            for(int i=0;i<3;i++){
                if(sizu>siz[v][i]){
                    for(int j=2;j>i;j--) siz[v][j]=siz[v][j-1],fr[v][j]=fr[v][j-1],zz[v][j]=zz[v][j-1];
                    siz[v][i]=sizu,fr[v][i]=u,zz[v][i]=zzu;
                    break;
                }
            }
            dfs2(v,u);
        }
    }
    dot[++cnt]={siz[u][0],siz[u][1],siz[u][2],u};//储存三元组+id
}

int trs[N+5],tri[N+5];
void upd(int x,int s,int id){//树状数组，trs为最大第三长链，tri为中心点
    for(;x<=n;x+=x&-x) if(s>trs[x]) trs[x]=s,tri[x]=id;
}
int ask(int x){
    int s=-1,id=0;
    for(;x;x-=x&-x) if(trs[x]>s) s=trs[x],id=tri[x];
    return id;//求的是中心点
}
int find(int x){//找到最长连符合条件的范围
    int l=1,r=n+1;
    while(r-l>1){
        int mid=l+r>>1;
        fuc[mid].x>=x? l=mid:r=mid;
    }return l;
}
int line(int u,int d,int x){
    if(!x) return u;
    int z=zz[u][d],len=dep[u]-dep[z],ans=u;
    if(x<=len){//在起点一侧
        for(int i=logn,y=(1<<logn);i>=0;i--,y>>=1) if(x&y) ans=fa[ans][i];
    }else{//在另一侧
        int fs=u;
        if(len){//转折点非自身
            for(int i=logn,y=(1<<logn);i>=0;i--,y>>=1) if((len-1)&y) fs=fa[fs][i];
            d=(dss[z][0]==fs);
        }else d=(fr[u][d]!=dss[u][0]);//转折点是自身
        x-=len+1,ans=dss[z][d];//跳到转折点的 重儿子/次重儿子
        for(int i=logn,y=(1<<logn);i>=0;i--,y>>=1) if(x&y) ans=ds[ans][i];//倍增
    }
    return ans;
}
int main(){
    memset(trs,-1,sizeof(trs));//初始值要为-1,不然为第三长为0的不会更新
    n=read(),logn=__lg(n);
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        g[u].push_back(v),g[v].push_back(u);
    }

    dfs1(1,-1),dfs2(1,-1);

    //对最长连进行离散化，以便用树状数组维护
    sort(dot+1,dot+1+n,cmp);
    fuc[1]={dot[1].x,1};
    for(int i=2;i<=n;i++) fuc[i]={dot[i].x,i};
    sort(fuc+1,fuc+1+n,cmp2);
    for(int i=1;i<=n;i++) xid[fuc[i].id]=i;

    q=read();
    for(int i=1;i<=q;i++){
        int x=read(),y=read(),z=read();
        x=x+y-z>>1,y-=x,z-=y,swap(y,z);
        ans[i][1]=1,ans[i][2]=2;
        if(x<y) swap(x,y),swap(ans[i][0],ans[i][1]);
        if(x<z) swap(x,z),swap(ans[i][0],ans[i][2]);
        if(y<z) swap(y,z),swap(ans[i][1],ans[i][2]);
        qs[i]={x,y,z,i};
    }
    sort(qs+1,qs+1+q,cmp);
    cnt=1;
    for(int i=1;i<=q;i++){
        int x=qs[i].x,y=qs[i].y,z=qs[i].z,id=qs[i].id;
        while(cnt<=n&&dot[cnt].y>=y) upd(xid[cnt],dot[cnt].z,dot[cnt].id),cnt++;
        int u=ask(find(x));
        int sss[3]={ans[id][0],ans[id][1],ans[id][2]};
        ans[id][sss[0]]=line(u,0,x),ans[id][sss[1]]=line(u,1,y),ans[id][sss[2]]=line(u,2,z);
    }
    for(int i=1;i<=q;i++) printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
}