题解：P12653 [KOI 2024 Round 2] 分数竞赛

Purslane · 2025-06-05 14:06:15 · 题解

Solution

伟大的安徽字典序队长 FS_NEO 指出：

考虑固定起点和终点怎么计算答案。也就是做线性序列。

设 pre_i 为从起点走 i 步获得的代价（不采取最优策略）。

那么最终的得分是：pre_t - \min_i pre_i；清零次数为 pre 的严格前缀最小值数量减一。

看到树上路径统计问题，想到点分治。

设分治中心是 root，我们会把路径拆成 u \to root \to v。

所以 u \to v 的 pre 折线实际上是 u \to root 和 root \to v 两条 pre 折线拼起来。如图所示：

以 u 开始的所有路径的 pre_t 之和是好算的。考虑怎么算 \min_i pre_i 之和。

对于蓝色的路径（从 u 出发），我们只需要知道 mn_1 和 sum_1；对于红色路径我们只需要知道 mn_2。拼在一起的最小值是 \min\{mn_1,sum_1+mn_2\}。随便维护一下 mn_2 就行（比如用线段树）。

那么前缀最小值个数呢？首先考虑蓝色区域的前缀最小值个数，它们是不受影响的。容易使用树上倍增求出每个位置之后的第一个比他低的谷，如图所示：

对于红色部分，如果一个位置是拼接之后的前缀最小值，那么一定是原序列的前缀最小值，并且满足 mn_1 > sum+mn_2。如果这个不等式成立，那么这个红色位置一定是前缀最小值，不管它的后面是什么。所以这个节点会对 sze_v 个点产生贡献。也容易使用线段树维护。

说起来容易，代码非常冗杂，而且有点卡常。

#include<bits/stdc++.h>
#define ll 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=3e5+10;const ll INF=1e12;
int n,dep[MAXN],FA[MAXN],fa[MAXN][20];
vector<pair<int,int>> G[MAXN];

ll pre[MAXN],mn[MAXN],mx[MAXN],ans1[MAXN],ans2[MAXN];
int sze[MAXN],cut[MAXN],mxs[MAXN];
inline void dfs1(const int u,const int f) {
    sze[u]=1,mxs[u]=0;
    for(auto pr:G[u]) {
        int v=pr.first,w=pr.second;
        if(v==f||cut[v]) continue ;
        dfs1(v,u),mxs[u]=max(mxs[u],sze[v]),sze[u]+=sze[v];
    }
    return ;
}
vector<int> bel[MAXN];
inline int find_core(const int u,const int f,const int al) {
    if(max(mxs[u],al-sze[u])<=al/2) return u;
    for(auto pr:G[u]) {
        int v=pr.first,w=pr.second;
        if(v==f||cut[v]) continue ;
        int tans=find_core(v,u,al);
        if(tans!=-1) return tans;
    }
    return -1;
}
inline void dfs2(const int u,const int f,const int LIM) {
    mx[u]=mn[u]=pre[u],sze[u]=1,FA[u]=f;
    if(f) mx[u]=max(mx[u],mx[f]),mn[u]=min(mn[u],mn[f]);
    if(f) {
        if(pre[f]>pre[u]) fa[u][0]=f,dep[u]=dep[f]+1;
        else if(pre[u]>=mx[f]) fa[u][0]=u,dep[u]=0;
        else {
            int pos=f;
            roff(i,LIM,0) if(pre[fa[pos][i]]<=pre[u]) pos=fa[pos][i];
            pos=fa[pos][0],fa[u][0]=pos,dep[u]=dep[pos]+1;
        }
        ffor(i,1,LIM) fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    else ffor(i,0,LIM) fa[u][i]=0;
    for(auto pr:G[u]) {
        int v=pr.first,w=pr.second;
        if(v==f||cut[v]) continue ;
        pre[v]=pre[u]+w,dfs2(v,u,LIM),sze[u]+=sze[v];
    }
    return ;
}
struct INFO {ll sze,val;int cnt;};
namespace SGT {
    const int MAXM=1.5e7+10;
    int tot=0;
    struct Node {int ls,rs;ll sze,val;int cnt;}t[MAXM];
    inline INFO operator +(const INFO A,const INFO B) {return {A.sze+B.sze,A.val+B.val,A.cnt+B.cnt};}
    inline void init(void) {return tot=0,void();}
    inline int get_node(void) {return ++tot,t[tot]={0,0,0,0,0},tot;}
    inline void update(int &u,const ll l,const ll r,const ll x,const int dsze,const ll dval,const int dcnt) {
        if(!u) u=get_node();
        t[u].sze+=dsze,t[u].val+=dval,t[u].cnt+=dcnt;
        if(l!=r) {
            ll mid=l+(r-l)/2;
            if(x<=mid) update(t[u].ls,l,mid,x,dsze,dval,dcnt);  
            else update(t[u].rs,mid+1,r,x,dsze,dval,dcnt);
        }
        return ;
    }
    inline INFO query(const int u,const ll l,const ll r,const ll x,const ll y) {
        if(!u) return {0,0,0};
        if(x<=l&&r<=y) return {t[u].sze,t[u].val,t[u].cnt};
        INFO ans={0,0,0};
        ll mid=l+(r-l)/2;
        if(x<=mid) ans=ans+query(t[u].ls,l,mid,x,y);
        if(y>mid) ans=ans+query(t[u].rs,mid+1,r,x,y);
        return ans;
    }
};
inline void mark(const int u,const int f,const int anc) {
    bel[anc].push_back(u);
    for(auto pr:G[u]) {
        int v=pr.first,w=pr.second;
        if(v==f||cut[v]) continue ;
        mark(v,u,anc);  
    }
    return ;
}
inline void solve(int u) {
    dfs1(u,0);
    if(sze[u]==1) return cut[u]=1,void();
    int lim=__lg(sze[u]/2);
    u=find_core(u,0,sze[u]);
    dep[u]=pre[u]=mn[u]=mx[u]=0,dfs2(u,0,lim);
    bel[u].clear(),bel[u].push_back(u);
    vector<int> T;
    for(auto pr:G[u]) {
        int v=pr.first;
        if(cut[v]) continue ;
        T.push_back(v); 
    }
    bel[u].clear(),bel[u].push_back(u);
    for(auto v:T) bel[v].clear(),mark(v,u,v);
    vector<int> S=T; S.push_back(u);

    SGT::init();
    int rt=0;ll ts=0;
    for(auto id:S) {
        for(auto v:bel[id]) {
            ll sum1=pre[v],mn1=pre[v]-mx[v];
            INFO L;
            if(rt) L={SGT::t[rt].sze,SGT::t[rt].val,SGT::t[rt].cnt};
            else L={0,0,0};
            INFO R=SGT::query(rt,-INF,INF,mn1-sum1,INF);
            L.sze=L.sze-R.sze,L.val=L.val-R.val,L.cnt=L.cnt-R.cnt;
            ans1[v]+=(sum1*(L.cnt+R.cnt)+ts)-(sum1*L.cnt+L.val+R.cnt*mn1);
            ans2[v]+=1ll*dep[v]*(L.cnt+R.cnt)+L.sze;
        }
        for(auto v:bel[id]) {
            ll dsze=0,dval=mn[v],dcnt=1;
            if(v!=u&&pre[v]<mn[FA[v]]) dsze=sze[v];
            SGT::update(rt,-INF,INF,mn[v],dsze,dval,dcnt),ts+=pre[v];
        }
    }
    SGT::init(),rt=0,ts=0,reverse(S.begin(),S.end());
    for(auto id:S) {
        for(auto v:bel[id]) {
            ll sum1=pre[v],mn1=pre[v]-mx[v];
            INFO L;
            if(rt) L={SGT::t[rt].sze,SGT::t[rt].val,SGT::t[rt].cnt};
            else L={0,0,0};
            INFO R=SGT::query(rt,-INF,INF,mn1-sum1,INF);
            L.sze=L.sze-R.sze,L.val=L.val-R.val,L.cnt=L.cnt-R.cnt;
            ans1[v]+=(sum1*(L.cnt+R.cnt)+ts)-(sum1*L.cnt+L.val+R.cnt*mn1);
            ans2[v]+=1ll*dep[v]*(L.cnt+R.cnt)+L.sze;
        }
        for(auto v:bel[id]) {
            ll dsze=0,dval=mn[v],dcnt=1;
            if(v!=u&&pre[v]<mn[FA[v]]) dsze=sze[v];
            SGT::update(rt,-INF,INF,mn[v],dsze,dval,dcnt),ts+=pre[v];
        }
    }

    cut[u]=1;
    for(auto v:T) solve(v);
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    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});
    }
    solve(1);
    cout<<1<<'\n';
    ffor(i,1,n) cout<<ans1[i]<<' '; cout<<'\n';
    ffor(i,1,n) cout<<ans2[i]<<' '; cout<<'\n';
    return 0;
}