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

· · 题解

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

话说这题为什么是蓝

据同机房大佬说这道题树剖寄了，lct不想写，想着有没有别的方法。

然后发现倒着往前做，每个点只要更新一次，但问题是怎样优化遍历顺序似的每条边没被经过太多次。

因为每次改的是路径，所以把一次修改(u,v)拆成(u,lca)和(v,lca)，再考虑把一条链缩成一个点，这样最多每个点和合并产生的新的一个点被遍历一次，总次数最多是n+q的。

做法就冰茶几，依次从下往上把路径上的点合并，每个集合的祖先定为深度最浅的那个，合并的时候维护集合的祖先的爹，下面集合 合于 上面集合就好了。

所以直接并查集+暴力遍历可以解决的样子，只怪赛场上犯傻了以为可以不用并查集直接改每个点的爹。。这样不能真正把它合为一个点，只有树为链时复杂度才对。。


#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
int a[MAXN],n,q,fa[MAXN];
int f[MAXN][23],dep[MAXN];
int q1[MAXN],q2[MAXN],tot=1;
int edge[MAXN*2],Next[MAXN*2];
int head[MAXN],ds[MAXN],d[MAXN];
void add(int x,int y)
{
    edge[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
void dfs(int u)
{
    dep[u]=dep[f[u][0]]+1;
    fa[u]=u,d[u]=f[u][0];
    for(int i=1;i<=22;i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i;i=Next[i])
    {
        int v=edge[i];
        if(v==f[u][0])
            continue;
        f[v][0]=u;
        ds[i/2]=v;
        dfs(v);
    }
}
int lca(int u,int v)
{
    if(dep[u]<dep[v])
        swap(u,v);
    for(int i=22;i>=0;i--)
        if(dep[f[u][i]]>=dep[v])
            u=f[u][i];
    if(u==v)return u;
    for(int i=22;i>=0;i--)
        if(f[u][i]!=f[v][i])
            u=f[u][i],v=f[v][i];
    return f[u][0];
}
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void join(int u,int v)
{
    int f1=find(u),f2=find(v);
    if(f1!=f2)fa[f1]=f2,d[f1]=d[f2];
}
void solve(int u,int v,int id)
{
    int now=find(u),pos=find(v);
    while(now!=pos){
        if(!a[now])a[now]=id;
        join(now,d[now]);
        now=find(now);
    }
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1);
    for(int i=1;i<=q;i++)
        scanf("%d%d",&q1[i],&q2[i]);
    for(int i=q;i>=1;i--)
    {
        int k=lca(q1[i],q2[i]);
        solve(q1[i],k,i);
        solve(q2[i],k,i);
    }
    for(int i=1;i<n;i++)
        printf("%d ",a[ds[i]]);
    return 0;
}