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