P11755 [COCI 2024/2025 #5] 树树 2 / Stablo II题解

· · 题解

一眼就认出了正解是树剖，甚至比【模板】重链剖分/树链剖分还简单。

时间复杂度 O(n\log^2{n})，卡一下常就能过。

如果会树剖的话只要边权转点权就行了。

我们可以把一条边的边权当作这条边深度较大的节点的点权。

如图，以样例 1 最终结果为例，节点内左边较大数字为编号，右边较小数字为转化后的点权，边上数字为边权。

AC code

#include<bits/stdc++.h>
#define int long long
#define nc() getchar()
using namespace std;
const int N=1e6+5;
int n,q,t[N<<2],uu[N],vv[N];
int head[N],ver[N<<1],nxt[N<<1],tot=0;//链式前向星三件套 
int top[N],id[N],dep[N],fa[N],size[N],son[N],tot2=0;//朴实无华的树剖 
//top重链的开端 
//id在线段树中的位置 
//dep节点深度
//fa节点父亲
//size子树大小 
//son重儿子 
inline int read(){
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57){
        if(ch=='-') f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57) x=x*10+ch-48,ch=nc();
    return x*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void add(int x,int y){//加边 
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void pushdown(int k,int l,int r,int mid){
    if(!t[k]) return;
    t[k<<1]=t[k];
    t[k<<1|1]=t[k];
    t[k]=0;
}
void change(int k,int l,int r,int x,int y,int z){//区间修改 
    if(x<=l && r<=y){
        t[k]=z;
        return;
    }
    int mid=l+r>>1;
    pushdown(k,l,r,mid);
    if(x<=mid) change(k<<1,l,mid,x,y,z);
    if(mid<y) change(k<<1|1,mid+1,r,x,y,z);
}
void change_chain(int x,int y,int z){//将x到y的路径上的边权修改为z 
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        change(1,1,n,id[top[x]],id[x],z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    if(x!=y) change(1,1,n,id[x]+1,id[y],z);
    //注意是in[x]+1，x和y的最近公共祖先的点权不修改 
}
int query(int k,int l,int r,int x){//单点查询
    if(l==r) return t[k];
    int mid=l+r>>1;
    pushdown(k,l,r,mid);
    if(x<=mid) return query(k<<1,l,mid,x);
    else return query(k<<1|1,mid+1,r,x);
}
void dfs1(int u,int father){
    fa[u]=father;dep[u]=dep[fa[u]]+1;size[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=ver[i];
        if(v==fa[u]) continue;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int top_){ 
    id[u]=++tot2;top[u]=top_;
    if(son[u]) dfs2(son[u],top_);
    for(int i=head[u];i;i=nxt[i]){
        int v=ver[i];
        if(v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<n;i++){
        uu[i]=read();vv[i]=read();//记录第i条边 
        add(uu[i],vv[i]);add(vv[i],uu[i]);
    }
    dfs1(1,0);dfs2(1,1);
    for(int i=1;i<=q;i++){
        int x=read(),y=read();
        change_chain(x,y,i);
    }
    for(int i=1;i<n;i++){
        if(dep[uu[i]]>dep[vv[i]]) write(query(1,1,n,id[uu[i]])),putchar(' ');
        else write(query(1,1,n,id[vv[i]])),putchar(' ');
        //一条边中深度较大的节点点权即这条边的边权
//不懂的话看上面的图 
    }
}