题解归档 - cf2228F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2228F
• 本地来源：problems/cf2228F/idea.md
• 题目链接：https://codeforces.com/contest/2228/problem/F
• 原始标题：cf2228F - Momoyo and the Network

思路

cf2228F - Momoyo and the Network

pattern: binary search answer, directed-edge path DP.

claim: For a target minimum component weight X, a path v0...vk is valid iff both endpoints satisfy side(v0,v1)>=X, side(vk,v{k-1})>=X, and every internal vertex vi satisfies side(v{i-1},vi)+side(v{i+1},vi)<=total-X, where side(u,v) is the weight of the component containing u after removing edge u-v.

necessary: After deleting the path edges, an internal vertex component is everything except the two neighbor-side components, so its weight is total-side(prev,cur)-side(next,cur). Endpoint components are exactly one directed edge side.

sufficient: These local conditions describe exactly the k+1 components produced by removing the path. If there is a valid path of length greater than k, any length-k subpath is also valid: a former internal endpoint has the remaining neighbor-side at most total-X by the internal condition.

check: Binary search X. Let dp[u->v] be the longest valid continuation after taking directed edge u->v, with u already the left endpoint and v current. At v, either stop if side(v,u)>=X, or move to neighbor z!=u if side(u,v)+side(z,v)<=total-X, adding 1+dp[v->z]. Directed messages are computed bottom-up for parent-to-child directions and top-down for child-to-parent directions. Per vertex, sorted neighbor-side weights and prefix top two values answer all exclusions.

brute/check: brute.cpp enumerates all simple paths of length k on small random trees and computes components after removing path edges. gen.cpp generates small positive-weight trees.

edge: tree diameter smaller than k, k=1, star tree, path tree, endpoint side exactly X, and large total weight.

代码

来源：problems/cf2228F/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int neg=-1000000000;
struct edge{
    int to,rev,dp;
    ll side;
};
int n,k;
ll allw;
vector<ll>a,sub;
vector<int>par,pidx,ord;
vector<vector<edge>>g;
void ae(int u,int v){
    int iu=g[u].size(),iv=g[v].size();
    g[u].push_back({v,iv,neg,0});
    g[v].push_back({u,iu,neg,0});
}
vector<int> calc(int v,const vector<int>&qs,ll x){
    int d=g[v].size();
    vector<tuple<ll,int,int>>it;
    it.reserve(d);
    for(int i=0;i<d;i++){
        int val=neg;
        if(g[v][i].dp>neg/2) val=g[v][i].dp+1;
        it.push_back({allw-g[v][i].side,val,i});
    }
    sort(it.begin(),it.end());
    vector<int>b1(d),b2(d),id1(d),id2(d),ans;
    int c1=neg,c2=neg,p1=-1,p2=-1;
    for(int i=0;i<d;i++){
        int val=get<1>(it[i]),id=get<2>(it[i]);
        if(val>c1){
            c2=c1; p2=p1;
            c1=val; p1=id;
        }else if(val>c2){
            c2=val; p2=id;
        }
        b1[i]=c1; b2[i]=c2; id1[i]=p1; id2[i]=p2;
    }
    for(int idx:qs){
        int res=neg;
        if(g[v][idx].side>=x) res=0;
        ll lim=g[v][idx].side-x;
        int pos=upper_bound(it.begin(),it.end(),make_tuple(lim,INT_MAX,INT_MAX))-it.begin()-1;
        if(pos>=0){
            int val=(id1[pos]==idx?b2[pos]:b1[pos]);
            res=max(res,val);
        }
        ans.push_back(res);
    }
    return ans;
}
bool check(ll x){
    for(int i=1;i<=n;i++) for(auto &e:g[i]) e.dp=neg;
    for(int oi=n-1;oi>=1;oi--){
        int v=ord[oi],p=par[v];
        vector<int>q={pidx[v]};
        int res=calc(v,q,x)[0];
        g[p][g[v][pidx[v]].rev].dp=res;
    }
    for(int oi=0;oi<n;oi++){
        int v=ord[oi];
        vector<int>q;
        for(int i=0;i<(int)g[v].size();i++){
            int to=g[v][i].to;
            if(par[to]==v) q.push_back(i);
        }
        vector<int>res=calc(v,q,x);
        for(int z=0;z<(int)q.size();z++){
            int i=q[z],to=g[v][i].to;
            g[to][g[v][i].rev].dp=res[z];
        }
    }
    for(int v=1;v<=n;v++){
        for(auto e:g[v]){
            if(e.side>=x&&e.dp>neg/2&&e.dp+1>=k) return true;
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T,u,v,i;
    cin>>T;
    while(T--){
        cin>>n>>k;
        a.assign(n+1,0);
        sub.assign(n+1,0);
        g.assign(n+1,{});
        allw=0;
        for(i=1;i<=n;i++){
            cin>>a[i];
            allw+=a[i];
        }
        for(i=1;i<n;i++){
            cin>>u>>v;
            ae(u,v);
        }
        par.assign(n+1,0);
        pidx.assign(n+1,-1);
        ord.clear();
        ord.reserve(n);
        ord.push_back(1);
        for(i=0;i<(int)ord.size();i++){
            u=ord[i];
            for(int j=0;j<(int)g[u].size();j++){
                v=g[u][j].to;
                if(v==par[u]) continue;
                par[v]=u;
                pidx[v]=g[u][j].rev;
                ord.push_back(v);
            }
        }
        for(i=n-1;i>=0;i--){
            u=ord[i];
            sub[u]+=a[u];
            if(par[u]) sub[par[u]]+=sub[u];
        }
        for(u=1;u<=n;u++){
            for(auto &e:g[u]){
                v=e.to;
                if(par[v]==u) e.side=allw-sub[v];
                else e.side=sub[u];
            }
        }
        if(!check(1)){
            cout<<-1<<"\n";
            continue;
        }
        ll l=1,r=allw,ans=1;
        while(l<=r){
            ll mid=(l+r)>>1;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }else r=mid-1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}