题解 CF1019E 【Raining season】
litble
2019-03-14 14:51:17
# 题目分析
个人博客->[here](https://blog.csdn.net/litble/article/details/88552839)
假设你准备把所有“可能”成为最长路径的路径都提取出来，显然是用树分治啦，这题中，边分治比点分治更方便。
边分治教学->[here](https://blog.csdn.net/litble/article/details/80853633)
边分治的套路，第一步将多叉树转为二叉树，对于新增加出来的边，它的$a$和$b$都是0。然后集中处理经过某一条边的路径，一条边将整棵树分为两个部分，这条路径由在这两个部分里的部分组成，于是我们要合并两个部分的信息。
什么是可能成为最长路径的路径？将每条路径看做一条直线$y=ax+b$，则做半平面交后，从平面最上方往下看能看到的线就是有可能的。但是半平面交是无法快速合并信息的，所以要半平面交对偶转凸包。
半平面交对偶转凸包教学->[here](http://trinkle.blog.uoj.ac/blog/235)，不过我也没看完，就是将直线$y=ax+b$转为点$(a,b)$，求一个下凸壳式的半平面交，相当于求一个上凸壳式的凸包。
然后将两边信息合并，相当于做两个凸壳的闵可夫斯基和，就是将两边凸壳存在的向量全部取出来，从大到小极角排序（归并即可），然后新凸壳第一个点为两个凸壳第一个点的$x$和$y$坐标分别相加的值，再让这个点依次按照每个向量移动，构成一个新凸壳。
然后将每个分治中心边上的凸壳上的点都丢在一起，最后再构造出一个新的答案凸壳，凸壳上的点数是$O(n \log n)$级别的。
最后求答案，二分（abs改编的题要二分，其实这题直接双指针扫就行），求$x$这个横坐标落在哪条直线上，就是用斜率为$-x$的直线去切凸壳。
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
int q=0;char ch=' ';
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
return q;
}
typedef double db;
typedef long long LL;
const int N=400005,inf=0x3f3f3f3f;
struct point{LL x,y;};
point operator + (point A,point B) {return (point){A.x+B.x,A.y+B.y};}
point operator - (point A,point B) {return (point){A.x-B.x,A.y-B.y};}
db operator * (point A,point B) {return (db)A.x*(db)B.y-(db)B.x*(db)A.y;}
bool cmp(point A,point B) {return A.x==B.x?A.y>B.y:A.x<B.x;}
int n,m,tot,mxx,rt;
int h[N],ne[N<<1],to[N<<1],vis[N],sz[N];point w[N<<1];
vector<int> tr1[N];vector<point> tr2[N];
void add(int x,int y,point z) {
to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;
to[++tot]=x,ne[tot]=h[y],h[y]=tot,w[tot]=z;
}
void pre_dfs(int x,int las) {
for(RI i=h[x];i;i=ne[i]) {
if(to[i]==las) continue;
tr1[x].push_back(to[i]),tr2[x].push_back(w[i]),pre_dfs(to[i],x);
}
}
void rebuild() {
tot=1;for(RI i=1;i<=n;++i) h[i]=0;
for(RI i=1;i<=n;++i) {
int sz=tr1[i].size();
if(sz<=2) {for(RI j=0;j<sz;++j) add(i,tr1[i][j],tr2[i][j]);}
else {
int o1=++n,o2=++n;
add(i,o1,(point){0,0}),add(i,o2,(point){0,0});
for(RI j=0;j<sz;++j)
if(j&1) tr1[o2].push_back(tr1[i][j]),tr2[o2].push_back(tr2[i][j]);
else tr1[o1].push_back(tr1[i][j]),tr2[o1].push_back(tr2[i][j]);
}
tr1[i].clear(),tr2[i].clear();
}
}
int st[N];vector<point> tmp,ans;
void build_cov(vector<point> &cov) {
sort(cov.begin(),cov.end(),cmp);
int top=0;
for(RI i=0;i<(int)cov.size();++i) {
if(i!=0&&cov[i].x==cov[i-1].x) continue;
while(top>1&&(cov[i]-cov[st[top-1]])*(cov[st[top]]-cov[st[top-1]])<0) --top;
st[++top]=i;
}
tmp.clear();for(RI i=1;i<=top;++i) tmp.push_back(cov[st[i]]);
swap(tmp,cov);
}
void add_cov(vector<point> &cov1,vector<point> &cov2,vector<point> &cov) {
if(cov1.empty()) {cov=cov2;return;}
if(cov2.empty()) {cov=cov1;return;}
cov.clear();point now=cov1[0]+cov2[0];
cov.push_back(now);
for(RI i=0,j=0,k=1;k<=(int)cov1.size()+(int)cov2.size()-2;++k) {
point v1,v2;
if(i<=(int)cov1.size()-2) v1=cov1[i+1]-cov1[i];
if(j<=(int)cov2.size()-2) v2=cov2[j+1]-cov2[j];
if(j>(int)cov2.size()-2||(i<=(int)cov1.size()-2&&v1*v2<0)) now=now+v1,++i;
else now=now+v2,++j;
cov.push_back(now);
}
}
vector<point> cov1,cov2;
void getrt(int x,int las,int SZ) {
sz[x]=1;
for(RI i=h[x];i;i=ne[i]) {
if(to[i]==las||vis[i>>1]) continue;
getrt(to[i],x,SZ),sz[x]+=sz[to[i]];
int bl=max(SZ-sz[to[i]],sz[to[i]]);
if(bl<mxx) mxx=bl,rt=i;
}
}
void dfs(int x,int las,point dis,vector<point> &cov) {
cov.push_back(dis);
for(RI i=h[x];i;i=ne[i])
if(to[i]!=las&&!vis[i>>1])
dfs(to[i],x,dis+w[i],cov);
}
void work(int x,int SZ) {
mxx=inf,getrt(x,0,SZ);
if(mxx==inf) return;
int now=rt;vis[now>>1]=1;
cov1.clear(),cov2.clear();
dfs(to[now],0,(point){0,0},cov1),dfs(to[now^1],0,w[now],cov2);
build_cov(cov1),build_cov(cov2),add_cov(cov1,cov2,tmp);
for(RI i=0;i<tmp.size();++i) ans.push_back(tmp[i]);
int ksz=sz[to[now]];work(to[now],ksz),work(to[now^1],SZ-ksz);
}
point binary_on_cov(LL x) {
int l=0,r=ans.size()-1;
point kv=(point){1,-x};
while(l<=r) {
int mid=(l+r)>>1;
if(mid>l&&kv*(ans[mid]-ans[mid-1])<0) r=mid-1;
else if(mid<r&&(ans[mid+1]-ans[mid])*kv<0) l=mid+1;
else return ans[mid];
}
}
int main()
{
int x,y,k,b;
n=read(),m=read();
for(RI i=1;i<n;++i)
x=read(),y=read(),k=read(),b=read(),add(x,y,(point){k,b});
pre_dfs(1,0),rebuild(),work(1,n),build_cov(ans);
for(RI t=0;t<m;++t) {
if(n==1) printf("0 ");
else {
point v=binary_on_cov(t);
printf("%lld ",v.x*t+v.y);
}
}
puts("");
return 0;
}
```