CXXXI.[GYM102331J]Jiry Matchings
首先，不难想到一个 \(O(n^2)\) 的树上背包：设 \(f_{i,0/1,j}\) 表示在以 \(i\) 为根的子树内，其中 \(i\) 没有被匹配/被匹配了，且整个子树中共匹配了 \(j\) 条边的最优方案。考虑优化。
我们知道一个结论——对于任意带权网络流图，随着总流量的增加，最大费用是凸函数，即差分不增的函数。这可以被这样证明：我们在 \(i-1\) 点流量的残量网络上多找到一条增广路，显然这条路一定与之前所有增广路相容。则其长度一定不大于 \(i-1\) 时的任一增广路，不然完全可以把那条短的增广路替换掉。
显然，最大带权匹配也是带权网络流模型，也因此 \(f_{i,0/1}\) 这两个函数理论上都是凸的。但实际上，因为 \(f_{i,1}\) 强制 \(i\) 被匹配上，故不一定最优；但我们如果修改 \(f_{i,1}\) 的定义为 \(i\) 可以被匹配，也可以不被匹配，则此时显然两个函数都是凸的。
我们考虑合并一条边连接着的两个子树（也即一对父子），不妨设父亲为 \(u\)，儿子为 \(v\)，则 \(f_{u,0}\times f_{v,0}\rightarrow f_{u,0},\max\Big(f_{u,0}\times e(u,v)\times f_{v,0},f_{u,1}\times f_{v,1}\Big)\rightarrow f_{u,1}\)。其中，\(\times\) 符号为我们接下来定义的一种卷积，其可以作用于数组与数组间、数组与整数间；\(e(u,v)\) 为连接 \((u,v)\) 的边的权值，对两个函数取 \(\max\) 意为对每一位分别取 \(\max\)。
下面我们来考虑如何定义卷积。明显，数组间的卷积，不妨设为 \(f=g\times h\)，则有
这个卷积对于普通的 \(g,h\) 函数是只有 \(O(n^2)\) 的计算方法的；但是，因为我们上文中出现的所有函数，按照我们之前的证明，都是凸的！我们再来看这个卷积，发现其本质是对于 \(g,h\) 在笛卡尔平面上形成的凸包的闵可夫斯基和，因为 \(g,h\) 均凸，所以是有 \(O(n)\) 的计算方法的！不考虑闵可夫斯基和的性质，我们也能得到，因为差分不增，所以若 \(f_i\) 从某一个 \(g_j+h_k\) 转移而来，则 \(f_{i+1}\) 一定是在 \(f_i\) 的基础上，加上 \(g_{j+1}-g_j\)，\(h_{k+1}-h_k\) 二者中较大的一个得到的。贪心地处理，即可做到 \(O(n)\)。
现在考虑数组与整数间卷积，明显就直接背包即可，也可 \(O(n)\) 直接得到。
于是我们合并一条边连接的子树的复杂度就是 \(O\Big(|u|+|v|\Big)\) 的，而非常规树上背包的 \(O\Big(|u||v|\Big)\)，但是这样还是改变不了我们树上背包 \(O(n^2)\) 的事实。
下面考虑祭出一些奇奇怪怪的合并方式。考虑对这棵树重链剖分。
现在，我们考虑先求出每个点仅考虑其所有轻儿子的子树时，其此时的 \(f_{i,0/1}\)。
明显，对于点 \(u\) 来说，仅考虑其一个轻儿子 \(v\) 时，其转移上来的东西是 \(f_{v,1}\rightarrow f_{u,0},\max\Big(f_{v,1},f_{v,0}\times e(u,v)\Big)\rightarrow f_{u,1}\)。
现在要求出其所有轻儿子转移上来的东西的卷积。如果直接按顺序一个一个乘的话，复杂度是 \(O(n^2)\) 的，因为每合并一个轻儿子，\(u\) 的函数大小就会增加，而我们卷积的复杂度是与 \(|u|\) 有关的，所用这样并不能保证复杂度。
但是，如果我们对其分治地进行合并的话，复杂度就是 \(O(n\log n)\) 的，因为每个轻儿子中所有元素都会被访问恰好 \(\log n\) 次。
显然，每个轻儿子仅会被转移一次，所以处理这个轻儿子的复杂度就是 \(O\Big(|u|\log n\Big)\) 的。因为关于树剖有一个结论，所有轻儿子的子树大小之和是 \(O(n\log n)\) 的，故此部分总复杂度是 \(O(n\log^2n)\) 的。
下面我们考虑重链部分的转移。显然，如果仍考虑归并地转移的话——显然，这里归并的状态就需要四个数组，即区间顶有/无被匹配、区间底有/无被匹配，且当归并到长度为 \(1\) 的区间时需要特殊考虑，因为此时区间的顶与底相同——复杂度仍为 \(O(n\log^2n)\)，因为此时链上所有节点所代表的子树两两无交，故单次重链合并的复杂度就是 \(O\Big(|u|\log n\Big)\) 的，其中 \(u\) 是链顶节点。而每个链顶节点也同时是某个东西的轻儿子，故此部分复杂度仍是 \(O(n\log^2n)\) 的。
总复杂度 \(O(n\log^2n)\)。实际实现时可以用 vector 模拟每个函数。不必担心空间、时间等常数问题，因为我写的非常随便的代码都没卡常过去了，事实上大概也跑不满。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x8080808080808080;
int n,head[200100],cnt;
struct node{int to,next,val;}edge[400100];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
struct Array:vector<ll>{
Array(){resize(1);}
friend Array operator +(const Array &u,const Array &v){
Array w;
w.resize(u.size()+v.size()-1);
for(int i=1,j=1,k=1;k<w.size();k++){
if(i==u.size()){w[k]=w[k-1]+v[j]-v[j-1],j++;continue;}
if(j==v.size()){w[k]=w[k-1]+u[i]-u[i-1],i++;continue;}
if(u[i]-u[i-1]>v[j]-v[j-1])w[k]=w[k-1]+u[i]-u[i-1],i++;
else w[k]=w[k-1]+v[j]-v[j-1],j++;
}
return w;
}
friend Array operator +(const Array &u,const int &v){
Array w=u;w.push_back(inf);
for(int i=1;i<w.size();i++)w[i]=max(w[i],u[i-1]+v);
return w;
}
friend Array operator |(const Array &u,const Array &v){
Array w;w.assign(max(u.size(),v.size()),inf);
for(int i=0;i<w.size();i++){
if(i<u.size())w[i]=max(w[i],u[i]);
if(i<v.size())w[i]=max(w[i],v[i]);
}
return w;
}
void print()const{for(auto i:*this)printf("%d ",i);puts("");}
};
struct Paira{
Array f,g;//f is the array for self matched-or-not, while g is the self not matched
Paira(){f=Array(),g=Array();}
Paira(Array F,Array G){f=F,g=G;}
friend Paira operator +(const Paira &u,const Paira &v){
Paira w;
w.f=(u.f+v.g)|(u.g+v.f);
w.g=u.g+v.g;
w.f=w.f|w.g;
// puts("U");u.print();
// puts("V");v.print();
// puts("W");w.print();
return w;
}
void print()const{printf("[1]"),f.print();printf("[0]"),g.print();}
}a[200100];
struct Quada{
Paira f,g;//f for upper matched-or-not, g for upper not matched
Quada(){f=Paira(),g=Paira();}
Quada(Paira F,Paira G){f=F,g=G;}
friend Quada merge(const Quada &u,const int &v,const Quada &w,bool U,bool W){
Quada r;
r.f.f=(u.f.f+w.f.f)|((u.f.g+w.g.f)+v);
r.f.g=(u.f.f+w.f.g);
if(W)r.f.g=r.f.g|((u.f.g+w.g.g)+v);
r.g.f=(u.g.f+w.f.f);
if(U)r.g.f=r.g.f|((u.g.g+w.g.f)+v);
r.g.g=(u.g.f+w.f.g);
if(U&&W)r.g.g=r.g.g|((u.g.g+w.g.g)+v);
r.f.g=r.f.g|r.g.g,r.g.f=r.g.f|r.g.g;
r.f.f=r.f.f|r.f.g|r.g.f;
// puts("U"),u.print();
// puts("W"),w.print();
// puts("R"),r.print();puts("");
return r;
}
void print()const{puts("[[F]]"),f.print();puts("[[G]]"),g.print();}
};
int fa[200100],son[201000],top[200100],sz[200100],val[200100];
void dfs1(int x){
sz[x]=1;
for(int i=head[x],y;i!=-1;i=edge[i].next){
if((y=edge[i].to)==fa[x])continue;
fa[y]=x,val[y]=edge[i].val,dfs1(y),sz[x]+=sz[y];
if(sz[y]>sz[son[x]])son[x]=y;
}
}
vector<int>v;
Paira lightsonsolve(int l,int r){
if(l==r-1)return Paira(a[v[l]].g+val[v[l]],a[v[l]].f);
int mid=(l+r)>>1;
return lightsonsolve(l,mid)+lightsonsolve(mid,r);
}
Quada heavysonsolve(int l,int r){
if(l==r)return Quada(Paira(a[v[l]].f,a[v[l]].g),Paira(a[v[l]].g,a[v[l]].g));
int mid=(l+r)>>1;
// printf("(%d,%d]:(%d,%d]+(%d,%d]\n",l,r,l,mid,mid,r);
return merge(heavysonsolve(l,mid),val[v[mid+1]],heavysonsolve(mid+1,r),l!=mid,mid+1!=r);
}
void dfs2(int x){
if(!top[x])top[x]=x;
if(son[x])top[son[x]]=top[x],dfs2(son[x]);
for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa[x]&&edge[i].to!=son[x])dfs2(edge[i].to);
v.clear();for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa[x]&&edge[i].to!=son[x])v.push_back(edge[i].to);
// printf("LIT%d:",x);for(auto i:v)printf("%d ",i);puts("");
if(!v.empty())a[x]=lightsonsolve(0,v.size());
// a[x].print();puts("");
if(top[x]!=x)return;
v.clear();for(int i=x;i;i=son[i])v.push_back(i);
// printf("CHA%d:",x);for(auto i:v)printf("%d ",i);puts("");
Quada tmp=heavysonsolve(0,v.size()-1);
a[x]=Paira(tmp.f.f,tmp.g.f);
}
int main(){
scanf("%d",&n),memset(head,-1,sizeof(head));
for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
dfs1(1),dfs2(1);
// for(int i=1;i<=n;i++)printf("%d %d %d %d %d\n",fa[i],son[i],top[i],sz[i],val[i]);
// for(int i=1;i<=n;i++)printf("%d:%d\n",i,a[i].f.size());
for(int i=1;i<n;i++)if(i<a[1].f.size())printf("%lld ",a[1].f[i]);else printf("? ");puts("");
return 0;
}