题意：
给出一棵树，每条边的距离都是一个一次函数，给出斜率k和截距m。（y=k*x+m）
现在求当x=0,1,2，……，t-1时，整个图中最远点的距离。
分析：
这题一股浓郁的OI气息啊。。。（思路简单实现复杂的数据结构题）
首先，如果不考虑那个神奇的边权，那么就是一个简单的点分治水题。。。
现在考虑加上这个边权，很容易发现，最终答案一定是一个下凸壳。
所以可以用一个multiset维护这个凸壳中的所有边，以及边之间的交点。由于每层有n个叶子节点，然后有logn层，所以总共的线段数不超过nlogn。。。
具体实现看代码吧，注释应该够详细了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
#define INF 0x3FFFFFFF
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
bool Q;
struct Line{mutable ll k,m,p;//slope,intercept,intersectionLine () {}Line (ll k1,ll m1,ll p1):k(k1),m(m1),p(p1) {}bool operator < (const Line & a) const {if(Q==1)return p<a.p;elsereturn k<a.k;}
};
typedef multiset<Line>::iterator mult ;
struct LC : multiset<Line>{
//maintain the lines,sperated by the intersectionll inf=1ll*INF*INF;ll flr(ll a,ll b){if((a^b)<0)return a/b-((a%b)!=0);elsereturn a/b;}bool compare(iterator x,iterator y){
//check: whether the x cover y or not (Slope of x is not bigger than y)if(y==end()){
//y is the end of the setx->p=inf;return 0;}if(x->k==y->k){
//compare the interceptif(x->m>y->m)x->p=inf;elsex->p=-inf; }elsex->p=flr(y->m - x->m,x->k - y->k);return x->p >= y->p;}void add(ll k,ll m){
//add the line with slope = k ,intercept = m in the setmultiset<Line>::iterator z=insert(Line(k,m,0));multiset<Line>::iterator y=z++;multiset<Line>::iterator x=y;while(compare(y,z))//compare the latterz=erase(z);if(x!=begin()&&compare(--x,y)){
//get the intersectiony=erase(y);compare(x,y); }y=x;while(y!=begin()&&(--x)->p>=y->p){
//compare the formery=erase(y);compare(x,y);y=x;}}ll que(ll x){Q=1;mult l=lower_bound(Line(0,0,x));Q=0;return l->k*x+l->m;}
}ans;
vector<int> a[MAXN];
vector<ll> K[MAXN],M[MAXN];
int siz[MAXN];
bool vis[MAXN];
int cent=-1,mins;
int dfs(int x,int fa){siz[x]=1;for(int i=0;i<a[x].size();i++){int u=a[x][i];if(u==fa||vis[u])continue;siz[x]+=dfs(u,x);}return siz[x];
}void find_c(int x,int fa,int sum){int mxsiz=sum-siz[x];for(int i=0;i<a[x].size();i++){int u=a[x][i];if(u==fa||vis[u])continue;mxsiz=max(mxsiz,siz[u]);find_c(u,x,sum);}if(cent==-1||mins>mxsiz){mins=mxsiz;cent=x; }
}int get_c(int x){if(vis[x]==1)return -1;cent=-1;mins=0; int sum=dfs(x,-1);find_c(x,-1,sum);return cent;
}
vector<pll> ans1;
void update_ans(const LC &a,const LC &b){
//merge and use them to update ansvector<pll> linea,lineb;for(mult it=a.begin();it!=a.end();it++){if(linea.size()>0&&linea[linea.size()-1].first==it->k){linea[linea.size()-1].second=max(linea[linea.size()-1].second,it->m);continue;}linea.push_back(make_pair(it->k,it->m));}for(mult it=b.begin();it!=b.end();it++){if(lineb.size()>0&&lineb[lineb.size()-1].first==it->k){lineb[lineb.size()-1].second=max(lineb[lineb.size()-1].second,it->m);continue;}lineb.push_back(make_pair(it->k,it->m));}int l=0,r=0;while(l<linea.size()&&r<lineb.size()){ans1.push_back(make_pair(linea[l].first+lineb[r].first,linea[l].second+lineb[r].second));if(l+1==linea.size())r++;else if(r+1==lineb.size())l++;else{double p1=-(double)(linea[l+1].second-linea[l].second)/(double)(linea[l+1].first-linea[l].first);double p2=-(double)(lineb[r+1].second-lineb[r].second)/(double)(lineb[r+1].first-lineb[r].first);if(p1<p2)l++;elser++;}}
}LC merge_trees(int l,int r,vector<LC> & s){
//merge the route from the different treesif(l==r){LC l0;l0.add(0,0);update_ans(l0,s[l]);return s[l];}else{int mid=(l+r)>>1;LC l1=merge_trees(l,mid,s);LC l2=merge_trees(mid+1,r,s); update_ans(l1,l2);for(mult it=l1.begin();it!=l1.end();it++)l2.add(it->k,it->m);return l2;}
}LC li;
void get_l(int x,int fa,ll prk,ll prm){
//dfs in the treebool flag=0;for(int i=0;i<a[x].size();i++){int u=a[x][i];if(u==fa||vis[u])continue;get_l(u,x,prk+K[x][i],prm+M[x][i]);flag=1;}if(!flag){li.add(prk,prm);//only the leaf can be the best}
}void solve(int x){
//solve the subtree with vertex xint centroid=get_c(x);if(centroid==-1)return ;vector<LC> s;for(int i=0;i<a[centroid].size();i++){int u=a[centroid][i];if(vis[u])continue;li.add(0,0);get_l(u,centroid,K[centroid][i],M[centroid][i]); s.push_back(li);li.clear();}if(s.size()>0)merge_trees(0,s.size()-1,s);vis[centroid]=1;for(int i=0;i<a[centroid].size();i++){int u=a[centroid][i];if(!vis[u]) solve(u);}
}
int n,t,u,v,k1,m1;
int main(){SF("%d%d",&n,&t); for(int i=1;i<n;i++){SF("%d%d%d%d",&u,&v,&k1,&m1); a[u].push_back(v);a[v].push_back(u);K[u].push_back(k1);K[v].push_back(k1);M[u].push_back(m1);M[v].push_back(m1);}solve(1);ans.add(0,0);for(int i=0;i<ans1.size();i++)ans.add(ans1[i].first,ans1[i].second);for(int i=0;i<t;i++)PF("%I64d ",ans.que(i));
}