题解：P17019 [ROI 2026 Day1] 泰莫利亚的调查

Unac_Zhou · 2026-11-09 21:58:15 · 题解

833B 的同学那里得到的排序除外线性且不需要复杂 dp 的做法。

问题转化为选择 k 个不交的祖先后代链，最大化链的长度和。

考虑弱化版：k 个任意祖先后代链，最大化所有链的并的长度和，即这个。

::::info[弱化版] 贪心，先选最长链，将这个链的所有边长变为 0，然后继续选最长链，选 k 次最长链即可。

:::info[贪心证明] 反证。如果不选最长链，考虑选的链中，有一条链和最长链交集最长，将这条链替换为最长链更优秀。 :::

若存在蓝色节点在选的链中，u 的儿子边有且仅有一个在选的链中，选的为红色边的最大值。（弱化版即选择所有红色边）

考虑改变一下树的形态转化为弱化版。类似网络流的思想，考虑最大值的本质为，对于所有数覆盖比它小的数，而选的链就是覆盖点的所有祖先。进而考虑如下建模。

不用真的建出来这个树，按照这个模型直接在原来的树上做即可。

:::success[code] 不卡常的题好好好好好评。

#include<bits/stdc++.h>
#define sz a[u].size()
#define bg a[u].begin()
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const ll N=5e5+10;
vector<pair<ll,ll>>a[N];
ll f[N],n,k,x,y,z,w;
ll dfs(ll u,ll fa){
    for(ll i=0;i<sz;i++)
    if(a[u][i].S==fa)
    {a[u].erase(bg+i); break;}
    a[u].pb({0,u}); ll b=0;
    sort(bg,a[u].end());
    for(ll i=sz-1;i;i--){
        ll t=dfs(a[u][i].S,u);
        f[++x]=min(t,b);
        b=max(t,b)+
        a[u][i].F-a[u][i-1].F;
    }
    return b;
}
int main(){
    scanf("%lld%lld",&n,&k);
    for(ll i=1;i<n;i++){
        scanf("%lld%lld",&x,&y);
        scanf("%lld",&z),w+=z*2;
        a[x].pb({z,y});
        a[y].pb({z,x});
    }
    x=0,y=dfs(1,0),f[++x]=y;
    sort(f+1,f+n+1);
    for(ll i=n;i>n-k;i--)
    printf("%lld\n",
    w-(f[i]+=f[i+1]));
    return 0;
}
:::
神秘卡常后即可多一个[黑题](https://www.luogu.com.cn/problem/P17851)。