题解：P11330 [NOISG 2022 Finals] Grapevine

RainySoul · 2025-01-20 08:27:25 · 题解

我来写一篇点分树题解。点分树无脑干就完了，但是为啥没人写呢？等你写完就知道了。。。。

淀粉树上每个点开一个线段树，下标按照这个连通块遍历的 \text{dfn} 序建。叶子节点维护连通块内每个点到当前点的 dis，其他节点就是区间 \min。

初始所有点皆为白点。

操作 1：查询距离点 x 最近的黑点。点分树上暴力跳祖先，查当前点到点分树上当前点子树内所有点的 dis 的 \min。最优化问题，来自同子树的一定不优，所以无需考虑消除 u 与 fa_u 子树内的重叠贡献。

操作 2：反转点 x 颜色。暴力跳祖先直接维护。

操作 3：修改一条边 (a,b) 的边权。首先边权变化动态维护 dis 可以使用树剖，边权转点权。然后考虑这个操作对当前场上的黑点是有影响的，前面按照连通块遍历 \text{dfn} 序的处理就是为这个操作服务的，这样可以保证每次涉及修改的点都是一个连续区间，从点分树上 a 和 b 的 \text{LCA} 开始暴力跳祖先，区间加。

一些麻烦的地方是你需要记录每一个连通块中每个点的 \text{dfn} 序，总点数是 O(n \log n) 级别的，需要一些动态的数据结构记录，这里使用平板电视中的 cc_hash_table。

看起来是不是非常简单！但是由于笔者很唐，他与这道题鏖战了一天，无敌了。

相信聪明的你一定可以很快切穿它的！

AC code：

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define inf 1e18
#define int long long
using namespace std;
using namespace __gnu_pbds;
const int N=100010,lgN=50;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

//树剖
struct SegementTree1{//这个是求dis用的树剖线段树
    int w[N<<2];
    inline void update(int u,int l,int r,int x,int k){
        if(l==r){
            w[u]=k;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid)update(u*2,l,mid,x,k);
        else update(u*2+1,mid+1,r,x,k);
        w[u]=w[u*2]+w[u*2+1];
    }
    inline int query(int u,int l,int r,int x,int y){
        if(x<=l&&r<=y)return w[u];
        int mid=(l+r)>>1;
        int res=0;
        if(x<=mid)res+=query(u*2,l,mid,x,y);
        if(y>mid)res+=query(u*2+1,mid+1,r,x,y);
        return res;
    }
}T1;
struct zyx{int to,w;};
vector<zyx> e[N];
struct csq{int u,v,w;};
vector<csq> edge;
int n,Q,cnt;
int fa[N],sz[N],dep[N],son[N],top[N],dfn[N],rnk[N];
inline void dfs1(int now,int fz){
    fa[now]=fz;
    sz[now]=1;
    dep[now]=dep[fz]+1;
    for(int i=0;i<(int)e[now].size();i++){
        int to=e[now][i].to;
        if(to==fz)continue;
        dfs1(to,now);
        sz[now]+=sz[to];
        if(sz[to]>sz[son[now]])son[now]=to;
    }
}
inline void dfs2(int now,int topf){
    top[now]=topf;
    dfn[now]=++cnt;
    rnk[cnt]=now;
    if(!son[now])return;
    dfs2(son[now],topf);
    for(int i=0;i<(int)e[now].size();i++){
        int to=e[now][i].to;
        if(to==fa[now]||to==son[now])continue;
        dfs2(to,to);
    }
}
int getdis(int x,int y){
    int res=0;
    while(top[x]!=top[y]){
        if(dep[top[y]]>dep[top[x]])swap(x,y);
        res+=T1.query(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[y]>dep[x])swap(x,y);
    res+=T1.query(1,1,n,dfn[y]+1,dfn[x]);
    return res;
}
//树剖

//建点分树
struct SegementTree2{
    int w[N*lgN],ls[N*lgN],rs[N*lgN],lazy[N*lgN];
    int rt[N],tot;
    inline void pushdown(int u){
        if(!lazy[u])return;
        w[ls[u]]+=lazy[u];
        w[rs[u]]+=lazy[u];
        lazy[ls[u]]+=lazy[u];
        lazy[rs[u]]+=lazy[u];
        lazy[u]=0;
    }
    inline void update1(int &u,int l,int r,int x,int k){//单点修改
        if(!u)u=++tot;
        if(l==r){
            w[u]=k;
            return;
        }
        int mid=(l+r)>>1;
        pushdown(u);
        if(x<=mid)update1(ls[u],l,mid,x,k);
        else update1(rs[u],mid+1,r,x,k);
        w[u]=min(w[ls[u]],w[rs[u]]);
    }
    inline void update2(int &u,int l,int r,int x,int y,int k){//区间加
        if(!u)u=++tot;
        if(x<=l&&r<=y){
            w[u]+=k;
            lazy[u]+=k;
            return;
        }
        int mid=(l+r)>>1;
        pushdown(u);
        if(x<=mid)update2(ls[u],l,mid,x,y,k);
        if(y>mid)update2(rs[u],mid+1,r,x,y,k);
        w[u]=min(w[ls[u]],w[rs[u]]);
    }
    inline void build(int &u,int l,int r){
        if(!u)u=++tot;
        w[u]=inf;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(ls[u],l,mid);
        build(rs[u],mid+1,r);
    }
}T2;
int maxnson[N],vis[N],FA[N],sum,rt,dep2[N],tcnt;
cc_hash_table<int,int> dfn2[N],sz2[N];
inline void getrt(int now,int fz){
    maxnson[now]=0;
    sz[now]=1;
    for(int i=0;i<(int)e[now].size();i++){
        int to=e[now][i].to;
        if(to==fz||vis[to])continue;
        getrt(to,now);
        sz[now]+=sz[to];
        maxnson[now]=max(maxnson[now],sz[to]);
    }
    maxnson[now]=max(maxnson[now],sum-sz[now]);
    if(maxnson[now]<maxnson[rt])rt=now;
} 
inline void dfs(int from,int now,int fa){
    dfn2[from][now]=++tcnt;//这里存一下每个点在以from为根的连通块中的dfn序与sz
    sz2[from][now]=1;
    for(int i=0;i<(int)e[now].size();i++){
        int to=e[now][i].to;
        if(to==fa||vis[to])continue;
        dfs(from,to,now);
        sz2[from][now]+=sz2[from][to];
    }
}
inline void solve(int now){
    vis[now]=1;tcnt=0;
    dfs(now,now,0);
    T2.build(T2.rt[now],1,sz2[now][now]);//给这棵线段树全开inf
    for(int i=0;i<(int)e[now].size();i++){
        int to=e[now][i].to;
        if(vis[to])continue;
        rt=0,sum=sz2[now][to];
        getrt(to,now);
        FA[rt]=now;dep2[rt]=dep2[now]+1;//dep2记录每个点在点分树上的深度
        solve(rt);
    }
}
//建点分树

//处理询问
inline int getans(int x){
    int res=inf,temp=x;
    while(temp){
        res=min(res,getdis(temp,x)+T2.w[T2.rt[temp]]/*直接查询点分树上temp子树的最小值*/);
        temp=FA[temp];
    }
    return res;
}
inline void Update(int x,int k){
    int temp=x;
    while(temp){
        int DIS=getdis(x,temp);
        if(k==1)T2.update1(T2.rt[temp],1,sz2[temp][temp],dfn2[temp][x],DIS);
        else if(k==-1)T2.update1(T2.rt[temp],1,sz2[temp][temp],dfn2[temp][x],inf);
        temp=FA[temp];
    }
}
inline void calc(int x,int y,int w){
    int p=x,q=y;
    if(dep2[p]<dep2[q])swap(p,q);
    while(dep2[p]>dep2[q])p=FA[p];
    while(p!=q)p=FA[p],q=FA[q];
    while(p){
        if(dfn2[p][x]<dfn2[p][y])swap(x,y);
        T2.update2(T2.rt[p],1,sz2[p][p],dfn2[p][x],dfn2[p][x]+sz2[p][x]-1,w);//线段树的r别手滑开到n去了
        p=FA[p];
    }
}
int yes[N],tot;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=read(),Q=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        e[u].push_back((zyx){v,w});
        e[v].push_back((zyx){u,w});
        edge.push_back((csq){u,v,w});
    }
    dfs1(1,0);dfs2(1,1);//树剖
    for(int i=0;i<n-1;i++){
        int u=edge[i].u,v=edge[i].v,w=edge[i].w;
        if(dep[u]<dep[v])swap(u,v);
        T1.update(1,1,n,dfn[u],w);
    }//下放边权
    rt=0,maxnson[rt]=inf,sum=n;
    getrt(1,0);
    solve(rt);
    for(int i=1;i<=Q;i++){
        int op=read();
        if(op==1){
            int q=read();
            if(tot==0)cout<<"-1\n";
            else cout<<getans(q)<<'\n';
        }
        else if(op==2){
            int u=read();
            if(yes[u]){
                yes[u]=0;
                tot--;
                Update(u,-1);
            }
            else if(!yes[u]){
                yes[u]=1;
                tot++;
                Update(u,1);
            }
        }
        else if(op==3){
            int a=read(),b=read(),w=read();
            if(dep[a]<dep[b])swap(a,b);
            calc(a,b,w-getdis(a,b));
            T1.update(1,1,n,dfn[a],w);
        }
    }
    return 0;
}