博主由于暂时退役失败又回来更博了。但是退役也快了。
亏死了，要不是 T2 数组开小了就 rk1 了。
A. 黑白沙漠
然而我并不会，先咕了。
B. 荒野聚餐
不妨设 (a_i) 表示雄性鸟人 (i) 的花费，(b_i) 表示雌性鸟人 (i) 的花费。列一下 LP：
[egin{aligned}
ext{minimize } S+sum_{i=1}^n a_i+b_i\
ext{s.t.}
egin{cases}
a_i+b_j+frac{S}{C} geq w_{i,j} ,forall i,j in [1,n]\
a_i geq 0,b_i geq 0,S geq 0
end{cases}
end{aligned}
]
这个限制不好看 于是考虑它的对偶问题：
[egin{aligned}
ext{maximize } sum_{i=1}^n sum_{j=1}^n w_{i,j}c_{i,j}\
ext{s.t.}
egin{cases}
sum_{j=1}^n c_{i,j} leq 1 ,forall i in [1,n]\
sum_{j=1}^n c_{j,i} leq 1 ,forall i in [1,n]\
sum_{i=1}^n sum_{j=1}^n c_{i,j} leq C
end{cases}
end{aligned}
]
发现是个网络流问题（你可以理解成 (n imes n) 的棋盘，每个点有一个颜色，每行每列至多只能选一个，所以就是大小为 (C) 的最大权匹配问题）
写个费用流能 77 分，题解上说写要求 KM 算法，我不会（你这个菜怎么啥都不会啊）
C. 火星在住
不妨设 (f_i) 表示选 (i) 条边的答案，发现可以建出费用流，并且要求流量(=i)，所以 (f) 是凸的。
考虑朴素dp：(f_{v,i,0/1}) (v) 这个点选了 (i) 条边，这个点有没有被选的答案。转移的时候是做的 ((max,+)) 卷积，由于是凸的，可以闵科夫斯基和合并凸包做到单次 (O(n))，于是你有了一个 (O(n^2)) 的做法。
链的做法有一个比较神奇的做法：每次从堆中取出最大的，设代价为 (w) ，设它左右两边点的代价为(w_l,w_r)，那么把 (w_l+w_r-w) 扔进堆里，并且删掉 (l,r) 。这样其实是部分模拟了费用流，但是难以拓展到树上。
可以快速合并两个数组了，我们考虑使用链分治。大概就是你先对树重链剖分，对于重链先求出每个重链上的点的 dp 数组，然后再重链上分治合并。求每个点的 dp 数组的时候有可能需要合并若干个轻儿子的 dp 数组，也需要分治合并。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <cassert>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 2e5 + 5;
struct Edge{
int to,w,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;
inline void add(int u,int v,int w){
e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
e[++cnt] = (Edge){u,w,head[v]};head[v] = cnt;
}
int val[MAXN],sz[MAXN],son[MAXN],tp[MAXN],fa[MAXN],n;
inline void dfs1(int v){
sz[v] = 1;
for(int i = head[v];i;i = e[i].nxt){
if(e[i].to == fa[v]) continue;
fa[e[i].to] = v;val[e[i].to] = e[i].w;dfs1(e[i].to);
sz[v] += sz[e[i].to];
if(sz[son[v]] < sz[e[i].to]) son[v] = e[i].to;
}
}
inline void dfs2(int v,int tp){
::tp[v] = tp;
if(son[v]) dfs2(son[v],tp);
for(int i = head[v];i;i = e[i].nxt){
if(e[i].to == fa[v] || e[i].to == son[v]) continue;
dfs2(e[i].to,e[i].to);
}
}
inline void upmax(int &x,int y){
if(x < y) x = y;
}
struct Poly{
std::vector<int> x;
inline int& operator [] (const int &n){return x[n];}
inline int deg(){return (int)x.size()-1;}
inline void ext(const int &n){x.resize(n+1);}
Poly(int n=-1){ext(n);FOR(i,0,n) x[i] = -1e18;}
inline void print(){
FOR(i,0,deg()) printf("%lld ",x[i]);puts("");
}
friend Poly operator + (Poly A,Poly B){
Poly res(A.deg()+B.deg());
int i = 0,j = 0;
while(i <= A.deg() && j <= B.deg()){
upmax(res[i+j],A[i]+B[j]);
if(i+1 > A.deg() || j+1 > B.deg()) break;
if(A[i+1]+B[j] >= A[i]+B[j+1]) ++i;
else ++j;
}
FOR(k,i+1,A.deg()) upmax(res[k+j],A[k]+B[j]);
FOR(k,j+1,B.deg()) upmax(res[i+k],A[i]+B[k]);
return res;
}
friend Poly operator + (Poly A,const int &d){
A.ext(A.deg()+1);
ROF(i,A.deg(),1) A[i] = A[i-1]+d;
A[0] = -1e18;
return A;
}
};
inline void upmax(Poly &A,Poly B){
// DEBUG(1);
FOR(i,0,B.deg()){
if(i > A.deg()) A.x.pb(B[i]);
else upmax(A[i],B[i]);
}
}
struct Node{
Poly f[2][2];
};
bool xxx;
inline Node merge(Node A,Node B,int w,bool flagl=0,bool flagr=0){
Node res;
FOR(i,0,1){
FOR(j,0,1){
upmax(res.f[i][j],A.f[i][0]+B.f[1][j]);
//if(xxx) res.f[0][0].print();
upmax(res.f[i][j],A.f[i][1]+B.f[0][j]);
//if(xxx) res.f[0][0].print();
upmax(res.f[flagl|i][flagr|j],(A.f[i][0]+B.f[0][j])+w);
upmax(res.f[i][j],A.f[i][0]+B.f[0][j]);
upmax(res.f[i][j],A.f[i][1]+B.f[1][j]);
}
}
return res;
}
Poly g[MAXN][2];
inline Node work(std::vector<int> &chain,int l,int r){
if(l == r){
Node res;
res.f[0][0] = g[chain[l]][0];
res.f[1][1] = g[chain[l]][1];
res.f[1][0].x.pb(-1e18);res.f[0][1].x.pb(-1e18);
return res;
}
int mid = (l + r) >> 1;
Node ll = work(chain,l,mid),rr = work(chain,mid+1,r);
// if(l == 0 && r == 2) xxx = 1,DEBUG(1);
Node t = merge(ll,rr,val[chain[mid+1]],mid-l+1==1,r-mid==1);
xxx = 0;
if(l == 0 && r == 2){
// DEBUG(l);DEBUG(r);
// FOR(i,0,1) FOR(j,0,1) ll.f[i][j].print();
// puts("");
// FOR(i,0,1) FOR(j,0,1) rr.f[i][j].print();
// puts("");
// FOR(i,0,1) FOR(j,0,1) t.f[i][j].print();
}
return t;
}
struct NODE{
Poly f[2];
};
inline NODE merge(NODE A,NODE B){
NODE res;
upmax(res.f[1],A.f[1]+B.f[0]);
upmax(res.f[1],A.f[0]+B.f[1]);
upmax(res.f[0],A.f[0]+B.f[0]);
return res;
}
inline NODE work2(std::vector<int> &chain,int l,int r){
if(l > r){
NODE res;
res.f[0].x.pb(0);res.f[1].x.pb(-1e18);
return res;
}
if(l == r){
NODE res;
res.f[1] = g[chain[l]][0]+val[chain[l]];
res.f[1][0] = -1e18;
upmax(res.f[0],g[chain[l]][0]);
upmax(res.f[0],g[chain[l]][1]);
return res;
}
int mid = (l + r) >> 1;
return merge(work2(chain,l,mid),work2(chain,mid+1,r));
}
inline void get1(int);
inline void get2(int);
inline void get1(int v){
std::vector<int> chain;
int now = v;
while(now) chain.pb(now),now = son[now];
FOR(i,0,(int)chain.size()-1) get2(chain[i]);
Node res = work(chain,0,(int)chain.size()-1);
upmax(g[v][0],res.f[0][0]);upmax(g[v][0],res.f[0][1]);
upmax(g[v][1],res.f[1][0]);upmax(g[v][1],res.f[1][1]);
// if(v == 1) g[v][0].print(),g[v][1].print();
}
inline void get2(int v){
g[v][0].x.pb(0);
g[v][1].x.pb(-1e18);
std::vector<int> chain;
for(int i = head[v];i;i = e[i].nxt){
if(e[i].to == fa[v] || e[i].to == son[v]) continue;
get1(e[i].to);chain.pb(e[i].to);
}
NODE res = work2(chain,0,(int)chain.size()-1);
upmax(g[v][1],res.f[1]);
upmax(g[v][0],res.f[0]);
}
signed main(){
int l,r;
scanf("%*d%lld%lld%lld",&n,&l,&r);
FOR(i,2,n){
int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);
}
dfs1(1);dfs2(1,1);
get1(1);
// DEBUG(g[1][0][2]);
// DEBUG(g[1][1][2]);
Poly ans;
upmax(ans,g[1][0]);upmax(ans,g[1][1]);
FOR(i,l,r){
if(i > ans.deg() || ans[i] < -9e17) printf("- ");
else printf("%lld ",ans[i]);
}
puts("");
return 0;
}