题意:给一棵树每条边有a,b两个值,给你一个m,表示从0到m-1,假设当前为i,那么每条边的权值是a*i+b,求该树任意两点的最大权值
题解:首先我们需要维护出(a,b)的凸壳,对于每个i在上面三分即可,点对用树分治维护,假设当前重心是u,那么把u的直接儿子挨个合并凸壳,这一过程用闵可夫斯基和维护,set启发式合并.
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(4)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define fi first
#define se second
#define db double
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
//#define C 0.5772156649
//#define ls l,m,rt<<1
//#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define ull unsigned long long
//#define base 1000000000000000000
#define fin freopen("a.txt","r",stdin)
#define fout freopen("a.txt","w",stdout)
#define fio ios::sync_with_stdio(false);cin.tie(0)
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}
template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}
using namespace std;
const ull ba=233;
const db eps=1e-5;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=100000+10,maxn=100000+10,inf=0x3f3f3f3f;
struct FastIO {
static const int S = 1e7;
int wpos;
char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar() {
static char buf[S];
static int len = 0, pos = 0;
if (pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if (pos == len) exit(0);
return buf[pos++];
}
inline int xuint() {
int c = xchar(), x = 0;
while (c <= 32) c = xchar();
for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
inline int xint()
{
int s = 1, c = xchar(), x = 0;
while (c <= 32) c = xchar();
if (c == '-') s = -1, c = xchar();
for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x * s;
}
inline void xstring(char *s)
{
int c = xchar();
while (c <= 32) c = xchar();
for (; c > 32; c = xchar()) * s++ = c;
*s = 0;
}
inline void wchar(int x)
{
if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos++] = x;
}
inline void wint(ll x)
{
if (x < 0) wchar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n) s[n++] = '0' + x % 10, x /= 10;
while (n--) wchar(s[n]);
wchar('
');
}
inline void wstring(const char *s)
{
while (*s) wchar(*s++);
}
~FastIO()
{
if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;
struct edge{int to,Next,a,b;}e[maxn<<1];
int cnt,head[N],sz[N],zx[N],n;
pll dis[N];
bool vis[N];
void init(){cnt=0;memset(head,-1,sizeof head);memset(vis,0,sizeof vis);}
void add(int u,int v,int a,int b){e[cnt].to=v;e[cnt].a=a;e[cnt].b=b;e[cnt].Next=head[u];head[u]=cnt++;}
void dfssz(int u,int f,int &sum)
{
sum++;sz[u]=1;
for(int i=head[u];~i;i=e[i].Next)
{
int x=e[i].to;
if(x==f||vis[x])continue;
dfssz(x,u,sum);sz[u]+=sz[x];
}
}
void dfszx(int u,int f,int sum,int &ans,int &id)
{
zx[u]=sum-sz[u];
for(int i=head[u];~i;i=e[i].Next)
{
int x=e[i].to;
if(x==f||vis[x])continue;
dfszx(x,u,sum,ans,id);
zx[u]=max(zx[u],sz[x]);
}
if(ans>zx[u]){ans=zx[u],id=u;}
}
int findzx(int root)
{
int sum=0;
dfssz(root,-1,sum);
int ans=inf,id=0;
dfszx(root,-1,sum,ans,id);
return id;
}
struct Point {
ll x, y;
Point(ll x = 0, ll y = 0) : x(x), y(y) {}
};
typedef Point Vector;
Point operator + (Vector A, Vector B) {return Point(A.x + B.x, A.y + B.y);}
Point operator - (Vector A, Vector B) {return Point(A.x - B.x, A.y - B.y);}
bool operator == (const Vector &A, const Point &B) {return A.x == B.x&& A.y == B.y;}
bool operator < (const Vector &A, const Vector &B) {return A.y < B.y || (A.y == B.y && A.x < B.x);}
ll Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}
int ConvexHull(Point *p, int n, Point *ch) {
sort(p, p + n);
int m = 0;
for(int i = 0; i < n; i++) {
while(m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;
ch[m++] = p[i];
}
int k = m;
for(int i = n - 2; i >= 0; i--) {
while(m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;
ch[m++] = p[i];
}
return n==1?m:m - 1;
}
int minkowski(Point *a,int &n,Point *b,int &m,Point *c,Point *d)
{
int top=0;
if(n<=2||m<=2)
{
for(int i=0;i<n;i++)for(int j=0;j<m;j++)
d[top++]=a[i]+b[j];
top=ConvexHull(d,top,c);
return top;
}
c[top++]=a[0]+b[0];
for(int i=0,j=0;i<n||j<m;)
{
Point p1=a[i%n]+b[(j+1)%m],p2=a[(i+1)%n]+b[j%m];
if(Cross(p1-c[top-1],p2-c[top-1])>=0)c[top++]=p1,++j;
else c[top++]=p2,++i;
}
return top-1;
}
Point a[N*40],b[N],c[N*4],d[N*4],ans[N*40];
vector<Point>v[N];
int top,la,lb;
void dfsdis(int u,int f,int root)
{
int num=0;
for(int i=head[u];~i;i=e[i].Next)
{
int x=e[i].to;
if(x==f||vis[x])continue;
num++;
dis[x].fi=dis[u].fi+e[i].a;
dis[x].se=dis[u].se+e[i].b;
dfsdis(x,u,root);
}
if(num==0)v[root].pb({dis[u].fi,dis[u].se});
}
void gao(int x)
{
la=0;
for(int i=0;i<v[x].size();i++)a[la++]=v[x][i];
lb=ConvexHull(a,la,b);v[x].clear();
for(int i=0;i<lb;i++)v[x].pb(b[i]);
}
void solve(int root)
{
int p=findzx(root);
v[0].clear();v[0].pb({0,0});
set<pii>s;s.clear();s.insert(mp(v[0].size(),0));
for(int i=head[p];~i;i=e[i].Next)
{
int x=e[i].to;if(vis[x])continue;
v[x].clear();
dis[x]=mp(e[i].a,e[i].b);dfsdis(x,p,x);
gao(x);s.insert(mp(v[x].size(),x));
}
while(s.size()>=2)
{
int x=s.begin()->se;s.erase(s.begin());
int y=s.begin()->se;s.erase(s.begin());
la=lb=0;
for(int i=0;i<v[x].size();i++)a[la++]=v[x][i];
for(int i=0;i<v[y].size();i++)b[lb++]=v[y][i];
int te=minkowski(a,la,b,lb,c,d);
for(int i=0;i<te;i++)ans[top++]=c[i];
for(int i=0;i<v[y].size();i++)v[x].pb(v[y][i]);v[y].clear();
gao(x);s.insert(mp(v[x].size(),x));
}
vis[p]=1;
for(int i=head[p];~i;i=e[i].Next)
{
int x=e[i].to;
if(vis[x])continue;
solve(e[i].to);
}
}
int main()
{
int n=io.xint(),m=io.xint();
init();
for(int i=1;i<n;i++)
{
int u=io.xint(),v=io.xint(),a=io.xint(),b=io.xint();
add(u,v,a,b);add(v,u,a,b);
}
solve(1);
top=ConvexHull(ans,top,a);
for(int i=0;i<m;i++)
{
int l=-1,r=top;
while(l<r-6)
{
int m=(l+r)>>1,m1=(m+r)>>1;
if(a[m].x*i+a[m].y>a[m1].x*i+a[m1].y)r=m1;
else l=m;
}
ll ma=0;
for(int j=max(0,l-10);j<min(top,l+10);j++)ma=max(ma,a[j].x*i+a[j].y);
io.wint(ma);
}
return 0;
}
/********************
********************/