题解：P11317 [RMI 2021] 路径 / Paths

· · 题解

Solution

奶龙题，但是为什么想了半个小时？？？

如果不换根，答案就是将树进行长链剖分后选前 k 大。

考虑换根的过程中直接维护所有的长链。发现从 u \to v，唯一的变化就是将某个数减去 w，再将另外一个数加上 w，求前 k 大。

这个问题咋做都行，随便写了一个线段树。（显然可以也 multiset）

刚开始把子树内、子树外的长链分开考虑了，然后发现必须可持久化……

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=4e5+10;
int n,k,mx_in[MAXN],mx_out[MAXN],lsh[MAXN],tot,ans[MAXN];
namespace DS {
    int cnt[MAXN<<2],sum[MAXN<<2];
    #define lson (k<<1)
    #define rson (k<<1|1)
    #define mid (l+r>>1)
    void update(int k,int l,int r,int pos,int dcnt,int dsum) {
        cnt[k]+=dcnt,sum[k]+=dsum;
        if(l==r) return ;
        if(pos<=mid) update(lson,l,mid,pos,dcnt,dsum);
        else update(rson,mid+1,r,pos,dcnt,dsum);
        return ;
    }
    int calc(int k,int l,int r,int c) {
        if(c>=cnt[k]) return sum[k];
        if(l==r) return lsh[l]*c;
        if(c<=cnt[rson]) return calc(rson,mid+1,r,c);
        return sum[rson]+calc(lson,l,mid,c-cnt[rson]);
    }
};
vector<pair<int,int>> G[MAXN],T[MAXN];
void dfs1(int u,int f) {
    for(auto pr:G[u]) {
        int v=pr.first,w=pr.second;
        if(v==f) continue ;
        dfs1(v,u),mx_in[u]=max(mx_in[u],mx_in[v]+w),T[u].push_back(pr);
    }
    return ;
}
void dfs2(int u,int f) {
    int mx=mx_out[u];
    for(auto pr:T[u]) {
        int v=pr.first,w=pr.second;
        mx_out[v]=max(mx_out[v],mx+w),mx=max(mx,mx_in[v]+w);
    }
    reverse(T[u].begin(),T[u].end()),mx=mx_out[u];
    for(auto pr:T[u]) {
        int v=pr.first,w=pr.second;
        mx_out[v]=max(mx_out[v],mx+w),mx=max(mx,mx_in[v]+w);
        lsh[++tot]=mx_in[v]+w,lsh[++tot]=mx_out[v]-w,lsh[++tot]=mx_in[v],lsh[++tot]=mx_out[v];
    }
    for(auto pr:T[u]) dfs2(pr.first,u);
    return ;
}
int find(int k) {return lower_bound(lsh+1,lsh+tot+1,k)-lsh;}
void dfs3(int u,int f) {
    int flg=0;
    for(auto pr:T[u]) {
        int v=pr.first,w=pr.second;
        if(mx_in[v]+w!=mx_in[u]||flg) DS::update(1,1,tot,find(mx_in[v]+w),1,mx_in[v]+w);
        else flg=1;
    }
    for(auto pr:T[u]) dfs3(pr.first,u);
    return ;
}
void dfs4(int u,int f) {
    ans[u]=DS::calc(1,1,tot,k);
    for(auto pr:T[u]) {
        int v=pr.first,w=pr.second;
        int del1=find(mx_in[v]+w),del2=find(mx_out[v]-w);
        int add1=find(mx_in[v]),add2=find(mx_out[v]);
        DS::update(1,1,tot,del1,-1,-(mx_in[v]+w));  
        DS::update(1,1,tot,del2,-1,-(mx_out[v]-w));
        DS::update(1,1,tot,add1,1,mx_in[v]);
        DS::update(1,1,tot,add2,1,mx_out[v]);
        dfs4(v,u);
        DS::update(1,1,tot,del1,1,mx_in[v]+w);  
        DS::update(1,1,tot,del2,1,mx_out[v]-w);
        DS::update(1,1,tot,add1,-1,-mx_in[v]);
        DS::update(1,1,tot,add2,-1,-mx_out[v]);
    }
    return ;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    ffor(i,1,n-1) {int u,v,w;cin>>u>>v>>w,G[u].push_back({v,w}),G[v].push_back({u,w});}
    dfs1(1,0),dfs2(1,0);
    sort(lsh+1,lsh+tot+1),tot=unique(lsh+1,lsh+tot+1)-lsh-1;
    DS::update(1,1,n,find(mx_in[1]),1,mx_in[1]),dfs3(1,0);
    dfs4(1,0);
    ffor(i,1,n) cout<<ans[i]<<'\n';
    return 0;
}