codeforces1019E Raining season 边分治+闵可夫斯基和+凸包

题目分析

假设你准备把所有“可能”成为最长路径的路径都提取出来，显然是用树分治啦，这题中，边分治比点分治更方便。

边分治教学->here

边分治的套路，第一步将多叉树转为二叉树，对于新增加出来的边，它的 a a a和 b b b都是0。然后集中处理经过某一条边的路径，一条边将整棵树分为两个部分，这条路径由在这两个部分里的部分组成，于是我们要合并两个部分的信息。

什么是可能成为最长路径的路径？将每条路径看做一条直线 y = a x + b y=ax+b y=ax+b，则做半平面交后，从平面最上方往下看能看到的线就是有可能的。但是半平面交是无法快速合并信息的，所以要半平面交对偶转凸包。

半平面交对偶转凸包教学->here，不过我也没看完，就是将直线 y = a x + b y=ax+b y=ax+b转为点 ( a , b ) (a,b) (a,b)，求一个下凸壳式的半平面交，相当于求一个上凸壳式的凸包。

然后将两边信息合并，相当于做两个凸壳的闵可夫斯基和，就是将两边凸壳存在的向量全部取出来，从大到小极角排序（归并即可），然后新凸壳第一个点为两个凸壳第一个点的 x x x和 y y y坐标分别相加的值，再让这个点依次按照每个向量移动，构成一个新凸壳。

然后将每个分治中心边上的凸壳上的点都丢在一起，最后再构造出一个新的答案凸壳，凸壳上的点数是 O ( n log ⁡ n ) O(n \log n) O(nlogn)级别的。

最后求答案，二分（abs改编的题要二分，其实这题直接双指针扫就行），求 x x x这个横坐标落在哪条直线上，就是用斜率为 − x -x −x的直线去切凸壳。

代码

#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;
}