BZOJ5341: [Ctsc2018]暴力写挂

BZOJ5341: [Ctsc2018]暴力写挂

https://lydsy.com/JudgeOnline/problem.php?id=5341

分析:

• 学习边分治。
• 感觉边分治在多数情况下都能用转二叉树后的点分治来写，不过反正都转二叉树了，不如写边分治。
• 对于这道题，最大化\(dep_x+dep_y-dep(lca1)+dep(lca2)\)
• \((dis(x,y)+dep_x+dep_y+dep(lca2))/2\)
• 其中\(dis(x,y)+dep_x+dep_y\)可以在分治过程中拆成\(w_x\)和\(w_y\)。
• 对第二棵树建虚树，枚举lca2,转化成求子树里颜色不同、在不同子树的两个点点权和最大。
• 多叉转二叉和之后的虚树\(dp\)什么的详见代码。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <vector>

#include <iostream>

using namespace std;

#define N 400050

#define db(x) cerr<<#x<<" = "<<x<<endl

char buf[100000],*p1,*p2;

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

int rd() {

	int x=0,f=1; char s=nc();

	while(s<'0') {if(s=='-')f=-1; s=nc();}

	while(s>='0') x=(((x<<2)+x)<<1)+s-'0',s=nc();

	return x*f;

}

typedef long long ll;

int n,c[N],a[N],is[N];

ll w[N],ans;

const ll inf=1ll<<55;

struct E {

	int t,v;

	E() {}

	E(int t_,int v_) {t=t_,v=v_;}

};

void run();

struct A {

	#define M 800050

	vector<E>V[N];

	int head[M],to[M<<1],nxt[M<<1],cnt,val[M<<1],m;

	int vis[M<<1],root,siz[M],fk[M<<1],tot;ll dis[M];

	void init(){cnt=1;}

	inline void add(int u,int v,int w) {

		to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;

	}

	void rb(int x,int y) {

		int i,lim=V[x].size(),so=0,lst=0;

		for(i=0;i<lim;i++) if(V[x][i].t!=y) {

			int t=V[x][i].t,v=V[x][i].v;

			so++;

			if(so==1) {

				add(x,t,v), add(t,x,v); lst=x;

			}else if(so==lim-(x!=1)) {

				add(lst,t,v), add(t,lst,v);

			}else {

				m++; add(lst,m,0); add(m,lst,0); add(m,t,v); add(t,m,v); lst=m;

			}

		}for(i=0;i<lim;i++)if(V[x][i].t!=y)rb(V[x][i].t,x);

	}void gd(int x,int y) {int i;for(i=head[x];i;i=nxt[i])if(to[i]!=y)dis[to[i]]=dis[x]+val[i],gd(to[i],x);}

	void gr(int x,int y) {

		int i; siz[x]=1;

		for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!vis[i]) {

			gr(to[i],x); siz[x]+=siz[to[i]]; fk[i]=max(siz[to[i]],tot-siz[to[i]]);

			if(fk[i]<fk[root]) root=i;

		}

	}

	void d1(int x,int y,ll d,int o) {

		int i;

		if(x<=n) c[x]=o, w[x]=dis[x]+d, a[++a[0]]=x, is[x]=1;

		for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!vis[i]) {

			d1(to[i],x,d+val[i],o);

		}

	}

	void dc(int x) {

		root=0;gr(x,0);if(!root)return;

		int p=root,all=tot;

		vis[p]=vis[p^1]=1;

		a[0]=0;

		d1(to[p],0,val[p],1);

		d1(to[p^1],0,0,2);

		run();

		int sz=siz[to[p]];

		tot=sz; dc(to[p]);

		tot=all-sz; dc(to[p^1]);

	}

	void pre() {

		int i,x,y,z;

		for(i=1;i<n;i++) x=rd(),y=rd(),z=rd(),V[x].push_back(E(y,z)),V[y].push_back(E(x,z));

		m=n; rb(1,0);

		gd(1,0);

	}

	void Wk() {

		tot=m; fk[0]=1<<30; dc(1);

	}

}t1;

inline bool cmp(const int&,const int&);

struct B {

	int head[N],to[N<<1],nxt[N<<1],cnt,val[N<<1];

	int dfn[N],fa[N],dep[N],siz[N],son[N],top[N];

	int S[N],tp;

	ll dis[N],f[N][3];

	inline void add(int u,int v,int w) {to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;}

	inline void add(int u,int v) {to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;}

	void d1(int x,int y) {

		dfn[x]=++dfn[0]; fa[x]=y; siz[x]=1; int i; dep[x]=dep[y]+1;

		for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {

			dis[to[i]]=dis[x]+val[i];

			d1(to[i],x); siz[x]+=siz[to[i]];

			if(siz[to[i]]>siz[son[x]]) son[x]=to[i];

		}

	}

	void d2(int x,int t) {

		top[x]=t;int i;if(son[x]) d2(son[x],t);

		for(i=head[x];i;i=nxt[i]) if(to[i]!=fa[x]&&to[i]!=son[x]) d2(to[i],to[i]);

	}

	int lca(int x,int y) {

		for(;top[x]!=top[y];y=fa[top[y]]) if(dep[top[x]]>dep[top[y]]) swap(x,y); return dep[x]<dep[y]?x:y;

	}

	void Wk() {

		int i,x,y,z; for(i=1;i<n;i++) x=rd(),y=rd(),z=rd(),add(x,y,z),add(y,x,z);

		d1(1,0); d2(1,1); memset(head,0,sizeof(head)); cnt=0;

	}

	void dp(int x) {

		int i;

		if(is[x]) f[x][c[x]]=w[x],f[x][3-c[x]]=-inf;

		else f[x][1]=f[x][2]=-inf;

		for(i=head[x];i;i=nxt[i]) {

			dp(to[i]);

			ans=max(ans,f[x][1]+f[to[i]][2]-2*dis[x]);

			ans=max(ans,f[x][2]+f[to[i]][1]-2*dis[x]);

			f[x][1]=max(f[x][1],f[to[i]][1]); f[x][2]=max(f[x][2],f[to[i]][2]);

		}

		head[x]=0; is[x]=0;

	}

	void mk() {

		cnt=0;

		int i;

		sort(a+1,a+a[0]+1,cmp);

		S[tp=1]=1;

		for(i=1;i<=a[0];i++) {

			int x=a[i],y=lca(x,S[tp]);

			while(dep[y]<dep[S[tp]]) {

				if(dep[y]>=dep[S[tp-1]]) {

					add(y,S[tp]); tp--;

					if(S[tp]!=y) S[++tp]=y;

					break;

				}

				add(S[tp-1],S[tp]); tp--;

			}

			if(S[tp]!=x) S[++tp]=x;

		}

		while(tp>1) add(S[tp-1],S[tp]),tp--;

		dp(1);

	}

}t2;

inline bool cmp(const int &x,const int &y) {return t2.dfn[x]<t2.dfn[y];}

void run() {t2.mk();}

int main() {

	n=rd();

	t1.init();

	t1.pre();

	t2.Wk();

	t1.Wk();

	ans>>=1;

	int i;

	for(i=1;i<=n;i++) {

		ans=max(ans,t1.dis[i]-t2.dis[i]);

	}

	printf("%lld\n",ans);

}