专栏文章

题解：P4695 [PA 2017] Banany

wwrkwrkwrk
P4695题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio5yba5
此快照首次捕获于
2025/12/02 13:54
3 个月前
此快照最后确认于
2025/12/02 13:54
3 个月前
查看原文
考虑树分块。这里所说的树分块是保证每个块的点的个数，并不保证每个块内部连通。
这里不是 P6177 的树分块！
使用随机撒点保证的是暴力跳父亲到关键点，而不是每个块的大小。
为啥不能保证连通？
考虑菊花图，显然中心点只能在一个连通块中。
使用如下方式：每次选取子树下的待选连通块，如果超过了阈值 BB 则用中心点虚拟连接，分到一块并且清空。最后剩下根的分成一块。这样可以保证大小在 [B,2B][B,2B] 之间。
块内信息更新后暴力重构即可，注意虚拟连接点的点权不认为是块内的，而是视作一个仅连接的特殊点。注意分别维护含和不含自己的。
考虑块间信息。我们需要找到这个点到另一个块的最近点然后减去距离。对于第一个问题，可以发现这个等价于块到块的最近距离的所在点。设 tit_i 表示实际的深度最小的点（虚拟点转实际点看），如果我们想知道从块 jj 出发第一个到 ii 的点，那么如果 tit_i 是 tjt_j 的祖先，那么就是从 tjt_j 开始的最近祖先且满足在 ii 中。否则就是 tit_i。
后面维护距离要求 O(1)O(1) 查询，考虑使用 O(1) lcaO(1) ~\text{lca} 转成维护深度，利用 DFS 序和使用 O(N)O(\sqrt N) 区间修改，O(1)O(1) 单点查询的分块数据结构即可完成。
理论时间复杂度 O(N+QN)O(N+Q\sqrt N)。实际运行时由于不能移到自身，故块内重构常数稍大，设 B=180B=180。
CPP
#include<bits/stdc++.h>
using namespace std;
bool st;
namespace _wrk{;
int dfn[200005];
int n,q;
vector<pair<int,long long>>g[200005];
namespace tools{
    int dfsid[200005],outid[200005];
    int pdep[200005];
    namespace o1lca{
        int fc[200005][21];
        void init(){
            for(int c=1;c<=20;c++){
                for(int i=1;i+(1ll<<c)-1<=n;i++){
                    fc[i][c]=fc[i][c-1];
                    if(pdep[fc[i][c-1]]>pdep[fc[i+(1ll<<(c-1))][c-1]])fc[i][c]=fc[i+(1ll<<(c-1))][c-1];
                }
            }
        }
        int query(int a,int b){
            if(a==b)return a;
            a=dfsid[a];b=dfsid[b];
            if(a>b)swap(a,b);
            b--;
            int len=b-a+1,p=__lg(len);
            int x=fc[a][p],y=fc[b-(1ll<<p)+1][p];
            if(pdep[x]>pdep[y])return y;
            return x;
        }
    }
    struct osqrtchao1qu{
        const int B=900;
        long long bl[200005],fc[200005];
        void ad(int l,int r,long long b){
            if(l!=0){
                ad(0,r,b);ad(0,l-1,-b);return;
            }
            int nc=0;
            while(nc+B-1<=r){
                bl[nc/B]+=b;
                nc+=B;
            }
            while(nc<=r){
                fc[nc]+=b;
                nc++;
            }
        }
        long long query(int a){
            return bl[a/B]+fc[a];
        }
    }zc;
    long long la[200005];
    void chapos(int x,long long y){
        long long delta=y-la[x];la[x]=y;
        zc.ad(dfsid[x],outid[x],delta);
    }
    void chaedge(int a,int b,long long c){
        int x=dfsid[a]>dfsid[b]?a:b;
        chapos(x,c);
    }
    long long getdep(int x){
        return zc.query(dfsid[x]);;
    }
    long long getlen(int a,int b){
        return getdep(a)+getdep(b)-2*getdep(o1lca::query(a,b));
    }
    int cnt=1;
    long long fpc[200005];
    void dfs(int now,int fa,long long fp){
        dfsid[now]=cnt++;
        pdep[now]=pdep[fa]+1;
        fpc[now]=fp;
        for(auto x:g[now]){
            int to=x.first;long long cost=x.second;
            if(to!=fa){
                o1lca::fc[cnt-1][0]=now;
                dfs(to,now,cost);
            }
        }
        outid[now]=cnt-1;
    }
    void init(vector<array<long long,3>>w){
        dfs(1,0,0);
        o1lca::init();
        for(int i=1;i<=n;i++){
            chapos(i,fpc[i]);
        }
        for(auto x:w){
            chaedge(x[0],x[1],x[2]);
        }
    }
    long long getlink(long long a){
        return la[a];
    }
}
int B;
long long p[200005];
list<int>bufc[200005];
int topc[200005],topid[200005];
int tcd[200005];
int bl,cic;
vector<int>cg[200005];
int xcr[200005];
void buildblock(const list<int>&sc,const vector<int>&z,int tid){
    bool f=0;
    for(auto x:sc){
        topc[x]=tid;
        topid[x]=bl;
        if(x==tid)f=1;
    }
    for(auto x:sc){
        for(auto y:g[x]){
            int to=y.first;
            if(topid[to]==topid[x]){
                cg[x].push_back(to);
            }
        }
    }
    if(!f){
        cic++;
        tcd[bl]=cic;
        xcr[cic]=tid;
        for(auto x:z){
            cg[x].push_back(cic);
            cg[cic].push_back(x);
        }
    }else{
        tcd[bl]=tid;
    }
    bl++;
}
void pdfs(int now,int fa){
    vector<int>tops;
    bufc[now].clear();
    for(auto x:g[now])if(x.first!=fa){
        pdfs(x.first,now);
        bufc[now].splice(bufc[now].end(), bufc[x.first]);//拼接
        tops.push_back(x.first);
        if(bufc[now].size()>=B){
            buildblock(bufc[now],tops,now);
            bufc[now].clear();
            tops.clear();
        }
    }
    bufc[now].push_back(now);
}
vector<int>b[200005];
int blo[1003][1003];
bool ue[1003];
void rdfs(int now,int fa){
    b[topid[now]].push_back(now);
    for(auto x:g[now]){
        int to=x.first;
        if(to!=fa){
            if(topid[to]!=topid[now]&&!ue[topid[to]]){
                for(int j=0;j<bl;j++){
                    if(j!=topid[to]&&b[j].size()){
                        blo[topid[to]][j]=b[j].back();
                    }
                }
                ue[topid[to]]=1;
            }
            rdfs(to,now); 
        }
    }
    b[topid[now]].pop_back();
}
void blockinit(){
    for(int i=0;i<=n;i++){
        topid[i]=-1;
        xcr[i]=i;
    }
    cic=n;
    pdfs(1,0);
    buildblock(bufc[1],{},1);
    rdfs(1,0);
    for(int i=0;i<bl;i++){
        for(int j=0;j<bl;j++){
            if(i!=j&&!blo[i][j]){
                blo[i][j]=tcd[j];
            }
        }
    }
}
struct fr{
    long long ans;int pid;
    fr(){
        ans=-1e18,pid=1e9;
    }
    fr(long long ans,int pid):ans(ans),pid(pid){}
};
bool operator>(const fr &a,const fr & b){
    return a.ans==b.ans?a.pid<b.pid:a.ans>b.ans;
}
bool operator<(const fr & a,const fr & b){
    return a.ans==b.ans?a.pid>b.pid:a.ans<b.ans;
}
bool operator==(const fr & a,const fr & b){
    return a.ans==b.ans&&a.pid==b.pid;
}
fr operator+(const fr & a,long long b){
    return {a.ans+b,a.pid};
}
fr operator-(const fr & a,long long b){
    return {a.ans-b,a.pid};
}
fr xc[200005];
fr xxc[200005];
void ddfs1(int now,int fa){
    xxc[now]=fr(-1e18,1e9);
    for(auto x:cg[now]){
        if(x!=fa){
            ddfs1(x,now);
            xxc[now]=max(xxc[now],xc[x]-tools::getlink(x));
        }
    }
    xc[now]=xxc[now];
    if(now<=n)xc[now]=max(xc[now],{p[now],now});
}
void ddfs2(int now,int fa,fr frp){
    fr ma1=fr(-1e18,1e9),ma2=fr(-1e18,1e9);
    auto inc=[&](const fr &x){
        if(x>ma1){
            ma2=ma1;ma1=x;
        }else if(x>ma2){
            ma2=x;
        }
    };
    xxc[now]=max(xxc[now],frp);
    xc[now]=max(xc[now],frp);
    if(fa){
        inc(frp);
    }
    for(auto x:cg[now]){
        if(x!=fa){
            inc(xc[x]-tools::getlink(x));
        }
    }
    if(now<=n){
        inc({p[now],now});
    }
    for(auto x:cg[now]){
        if(x!=fa){
            long long s=tools::getlink(x);
            auto p=xc[x]-s;
            if(p==ma1){
                ddfs2(x,now,ma2-s);
            }else{
                ddfs2(x,now,ma1-s);
            }
        }
    }
}
void rebuild(int blockid){
    ddfs1(tcd[blockid],0);
    ddfs2(tcd[blockid],0,fr(-1e18,1e9));
}
signed main(){
    B=180;
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    if(n==1){
        while(q--)cout<<"1\n";
        return 0;
    }
    for(int i=1;i<=n;i++)cin>>p[i];
    vector<array<long long,3>>ww;
    for(int i=1;i<n;i++){
        int a,b;long long w;
        cin>>a>>b>>w;
        g[a].push_back({b,w});
        g[b].push_back({a,w});
        ww.push_back({a,b,w});
    }
    tools::init(ww);
    blockinit();
    for(int i=0;i<bl;i++){
        rebuild(i);
    }
    int now=1;
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            long long x,q;
            cin>>x>>q;
            p[x]=q;
            rebuild(topid[x]);
        }else{
            long long a,b,c;
            cin>>a>>b>>c;
            tools::chaedge(a,b,c);
            int f=tools::pdep[a]>tools::pdep[b]?a:b;
            rebuild(topid[f]);
        }
        fr res=xxc[now];
        for(int i=0;i<bl;i++){
            if(i!=topid[now]){
                fr p=xc[blo[topid[now]][i]];
                p=p-tools::getlen(now,xcr[blo[topid[now]][i]]);
                res=max(res,p);
            }
        }
        cout<<res.pid<<' ';
        now=res.pid;
    }
    return 0;
}
}
bool en;
signed main(){
          return _wrk::main();
}
AC 记录。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...