WC2018 通道与 CTSC2018 暴力写挂

https://www.luogu.com.cn/problem/P4220
https://www.luogu.com.cn/problem/P4565

两个都给出点分治的做法，看起来边分治不光跑的慢还没什么不可替代性？

暴力写挂
考虑那个式子有两个不同树上的 \(\operatorname{LCA}\)，不好处理，考虑怎么换成一个
由于 \(dis(x,y)=deep(x)+deep(y)-2deep(\operatorname{LCA}(x,y))\)，于是用 \(dis\) 代换：\(\dfrac{1}{2}(dis(x,y)+deep(x)+deep(y)-2deep'(\operatorname{LCA'}(x,y)))\)，后面省略那个 \(\frac{1}{2}\)
可以先对第一个树进行点分治，设当前的分治中心是 \(u\)，那么式子就变成了 \(dis(u,x)+dis(u,y)+deep(x)+deep(y)-2deep'(\operatorname{LCA'}(x,y))\)
设 \(w(x)=dis(u,x)+deep(x)\)，这个可以一遍 dfs 求出
那么要求的东西最终就变成了 \(w(x)+w(y)-2deep'(\operatorname{LCA'}(x,y))\)，这个还要求 \(x,y\) 来源于 \(u\) 的不同的子树
可以把当前要分治的联通块拿出来，在第二课树上建立虚树，虚树上 dp，设 \(f(u,0)\) 表示 \(u\) 子树内 \(w(x)\) 最大的点，\(f(u,1)\) 表示次大、且满足和最大点在第一棵树中不属于同一子树的点
转移简单，在 \(\operatorname{LCA}\) 处更新答案即可

对于原本不在当前要分治的联通块，但是因为结构需要被加入虚树的点，可以以他为 \(\operatorname{LCA}\) 更新答案，但是不能用他的 \(w\) 初始化 \(f(u,0)\)
st 表求 \(\operatorname{LCA}\) 加上基数排序实现线性建虚树可以做到 \(O(n\log n)\)

#define N 400006
#define M 800006
#define LOG_N 20
struct Graph{
	int fir[N],nex[M],to[M],w[M],tot;
	inline void add(int u,int v,int c=0,int flag=1){
		to[++tot]=v;nex[tot]=fir[u];fir[u]=tot;w[tot]=c;
		if(flag) add(v,u,c,0);
	}
};
int n;
Graph T;
int st[LOG_N][N*2],lg2[N*2];
int dfscnt,dfn[N],id[N*2];
int deep[N];
long long sumT[N];
void dfsT(int u,int fa=0){
	deep[u]=deep[fa]+1;dfn[u]=++dfscnt;id[dfscnt]=u;
	for(int v,i=T.fir[u];i;i=T.nex[i]){
		v=T.to[i];
		if(v==fa) continue;
		sumT[v]=sumT[u]+T.w[i];
		dfsT(v,u);id[++dfscnt]=u;
	}
}
inline int getLca(int u,int v){
	if(dfn[u]>dfn[v]) lib::swap(u,v);
	u=dfn[u];v=dfn[v];
	int len=lg2[v-u+1];
	return deep[st[len][u]]>1]+1,st[0][i]=id[i];
	for(int j=1;jb.ans;}
};
inline void update(Ans &u0,Ans &u1,const Ans &max,const Ans &max2){
	static Ans id[4];
	id[0]=u0;id[1]=u1;id[2]=max;id[3]=max2;
	std::sort(id,id+4);
	u0=id[0];
	for(int j=1;;j++)if(id[j].col^id[0].col){
		u1=id[j];break;
	}
}
int real[N],realId;//is vertex u really exist?
Ans f[N][2];
long long ans;
void dp(int u,int fa=0){
	f[u][0]=f[u][1]=(Ans){-1,-_LL_INF};
	if(real[u]==realId) f[u][0]=(Ans){col[u],w[u]};
	for(int v,i=H.fir[u];i;i=H.nex[i]){
		v=H.to[i];
		if(v==fa) continue;
		dp(v,u);
		lib::chkMax(ans,f[u][0].ans+(f[u][0].col==f[v][0].col?f[v][1].ans:f[v][0].ans)-(sumT[u]<<1));
		lib::chkMax(ans,f[u][1].ans+(f[u][1].col==f[v][0].col?f[v][1].ans:f[v][0].ans)-(sumT[u]<<1));
		update(f[u][0],f[u][1],f[v][0],f[v][1]);
	}
}
Graph G;
long long sumG[N];
void pre(int u,int fa=0){
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(v==fa) continue;
		sumG[v]=sumG[u]+G.w[i];pre(v,u);
	}
}
int root,maxson[N],vis[N],size[N];
void dfs(int u,int color,int *a,int fa=0){
	real[u]=realId;
	col[u]=color;a[++a[0]]=u;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(v==fa||vis[v]) continue;
		w[v]=w[u]+G.w[i];dfs(v,color,a,u);
	}
	w[u]+=sumG[u];
}
inline void calc(int u){//root: u
	static int a[N];
	a[0]=col[0]=0;
	a[++a[0]]=u;col[u]=++col[0];w[u]=0;
	real[u]=++realId;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(vis[v]) continue;
		col[0]++;w[v]=w[u]+G.w[i];dfs(v,col[0],a);
	}
	w[u]+=sumG[u];
	build(a[0],a);
	dp(1);
}
void findRoot(int u,int fa=0){
	size[u]=1;maxson[u]=0;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(v==fa||vis[v]) continue;
		findRoot(v,u);size[u]+=size[v];
		lib::chkMax(maxson[u],size[v]);
	}
	lib::chkMax(maxson[u],size[0]-size[u]);
	if(maxson[u]size[u]?(tot-size[u]):size[v];
		findRoot(v);divide(root,size[v]);
	}
}
int main(){
		#ifdef LOCAL
		freopen("wronganswer20.in","r",stdin);
		#endif
	n=read();
	for(int u,v,i=1;i>=1;
	for(int i=1;i<=n;i++) lib::chkMax(ans,sumG[i]-sumT[i]);
	writeEN(ans);
	return RET;
}

通道
和上一个一样，还是想办法通过枚举一些东西来减少变化的量，尽量让变化的东西都在一个树上，尤其是减少式子中在多个树上求 \(\operatorname{LCA}\) 的情况
考虑在第一个树上点分治，分治中心是 \(u\)，然后在第二个树上枚举 \(p\) 表示这两个点 \(x,y\) 在第二个树上的 \(\operatorname{LCA}\)
式子变成了：\(dis_1(x,u)+dis_1(y,u)+deep_2(x)+deep_2(y)-2deep_2(p)+dis_3(x,y)\)，需要保证 \(x,y\) 在第一、第二棵树上都来自不同的子树
对第二课建立虚树，在第二课树上来自的子树不同很好保证，只需要注意一下啊更新答案、合并 dp 数组的顺序即可
发现如果要满足在第一颗树上来自 \(u\) 的不同子树，那么很难设计出这个 dp，考虑每次只合并 \(u\) 的两个子树

可以证明：若给树分成两类点，那么分别求出两端点都是同一类点的两条直径，会得到四个端点，那么两端点不是同一类点的直径的端点，一定在这四个点中

据此，维护 \(f(u,0/1)\) 表示第二课树的子树 \(u\) 内的所有点，在第三课树上组成的直径（两端点都是第一、第二类点）最长是多少、端点是啥
更新答案的时候，就可以对于每个孩子 \(v\)，把他们的端点稍微组合组合就行了
把 \(f(v,0/1)\) 合并到 \(f(u,0/1)\) 的时候，仍然应用上面的性质，就把 \(v\) 里面的点算作一类点，剩下的算作另一类，拿出端点来组合一下

至此解决了每次合并 \(u\)（分治中心）的两棵子树的问题，发现边分治的话因为是每次找中心边，一共只有两个子树，已经做完了。但是想要一个点分治的做法
我们把 \(u\) 的所有子树按照大小排序，按照合并果子的方式来合并他们（每次合并两个），最后再把所有子树和 \(u\) 合并一次
这样做如果每次合并的复杂度是 \(O(size_a+size_b)\) 的，那么点分治的总复杂度仍然是 \(O(n\log n)\) 的

简略证明，对合并的过程建哈夫曼树，那么大小为 \(s\) 的联通块在哈夫曼树上的深度是 \(\log \frac{s}{n}\)，于是有：

\[T(u)=\sum_{u\rightarrow v}T(v)+\sum_{u\rightarrow v} size_v\log \frac{size_v}{n} \]

\[T(u)=\sum_{u\rightarrow v}T(v)+\sum_{u\rightarrow v} size_v\log n-\sum_{u\rightarrow v} size_v\log size_v \]

\[T(u)=size_u\log n+\sum_{u\rightarrow v}T(v)-\sum_{u\rightarrow v} size_v\log size_v \]

然后你发现这样加上去中间的项都消了，最后就剩一个 \(O(n\log n)\)

线性建虚树，并精细实现合并果子的过程：先基数排序，然后用两个队列维护。可以做到 \(O(n\log n)\)
但懒得这么写了，写的 \(O(n\log^2 n)\) 已经排进了洛谷最优解第一页。。。感觉要是再去个 \(\log\) 就最优解了（

#define N 100006
#define M 200006
#define LOG_N 18
int lg2[N*2];
struct Graph{
	int fir[N],nex[M],to[M],tot;
	long long w[M];
	inline void add(int u,int v,long long c,int flag=1){
		to[++tot]=v;nex[tot]=fir[u];fir[u]=tot;w[tot]=c;
		if(flag) add(v,u,c,0);
	}
	inline void clear(){std::memset(fir,0,sizeof fir);tot=0;}
	inline void read(int n){for(int i=1,u,v;i>1]+1,st[0][i]=id[i];
		for(int j=1;j<=LOG_N;j++)for(int i=1;i+(1<dfn[v]) lib::swap(u,v);
		u=dfn[u];v=dfn[v];
		int o=lg2[v-u+1];
		return deep[st[o][u]]dis)&&(x=o.x,y=o.y,dis=o.dis);}
	inline Node operator + (const Node &o)const{
		if(!x) return o;
		if(!o.x) return *this;
		Node ans=*this;ans.chkMax(o);
		ans.chkMax(Node(x,o.x));ans.chkMax(Node(x,o.y));
		ans.chkMax(Node(y,o.x));ans.chkMax(Node(y,o.y));
		return ans;
	}
};
Node f[N][2];
inline void update(int u,int v){
	lib::chkMax(ans,calc(f[u][0].x,f[v][1].x)-(T2.sum[u]<<1));lib::chkMax(ans,calc(f[u][0].x,f[v][1].y)-(T2.sum[u]<<1));
	lib::chkMax(ans,calc(f[u][0].y,f[v][1].x)-(T2.sum[u]<<1));lib::chkMax(ans,calc(f[u][0].y,f[v][1].y)-(T2.sum[u]<<1));
	lib::chkMax(ans,calc(f[u][1].x,f[v][0].x)-(T2.sum[u]<<1));lib::chkMax(ans,calc(f[u][1].x,f[v][0].y)-(T2.sum[u]<<1));
	lib::chkMax(ans,calc(f[u][1].y,f[v][0].x)-(T2.sum[u]<<1));lib::chkMax(ans,calc(f[u][1].y,f[v][0].y)-(T2.sum[u]<<1));
	f[u][0]=f[u][0]+f[v][0];f[u][1]=f[u][1]+f[v][1];
}
inline void build(int n,int *node,const Graph &G){//build virtual tree from G
	std::sort(node+1,node+1+n,[&](const int &a,const int &b){return G.dfn[a]&ve,int fa=0){
	ve.push_back(u);
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(v==fa||vis[v]) continue;
		dis[v]=dis[u]+G.w[i];dfs(v,ve,u);
	}
}
struct Node{
	int u,size;
	inline int operator < (const Node &o)const{return size==o.size?uve[N];
inline void calc(int u,int tot){//tot: size of the block
	std::setset;
	static int node[N];
	dis[u]=0;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(vis[v]) continue;
		dis[v]=dis[u]+G.w[i];
		dfs(v,ve[v]);set.insert((Node){v,size[v]>size[u]?(tot-size[u]):size[v]});
	}
	while(set.size()>=2){
		Node aa=*set.begin(),bb=*(++set.begin());
		set.erase(set.begin());set.erase(set.begin());
		int a=aa.u,b=bb.u;
		node[0]=0;
		if(ve[a].size()>ve[b].size()) std::swap(a,b);
		for(int v:ve[b]) node[++node[0]]=v,color[v]=1;
		for(int v:ve[a]) node[++node[0]]=v,ve[b].push_back(v),color[v]=0;
		VirtualT::work(node[0],node);
		set.insert((Node){b,aa.size+bb.size});
	}
	node[0]=0;node[++node[0]]=u;color[u]=0;
	int a=(*set.begin()).u;
	for(int v:ve[a]) node[++node[0]]=v,color[v]=1;
	VirtualT::work(node[0],node);
	for(int i=G.fir[u];i;i=G.nex[i]) std::vector().swap(ve[G.to[i]]);
}
void findRoot(int u,int fa=0){
	size[u]=1;maxson[u]=0;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(v==fa||vis[v]) continue;
		findRoot(v,u);size[u]+=size[v];
		lib::chkMax(maxson[u],size[v]);
	}
	lib::chkMax(maxson[u],size[0]-size[u]);
	if(maxson[u]size[u]?(tot-size[u]):size[v];
		findRoot(v);divide(root,size[v]);
	}
}
inline void work(int n){
	root=0;maxson[0]=_INT_INF;size[0]=n;
	findRoot(1);divide(root,size[1]);
}
}//namespace Divide
int main(){
		#ifdef LOCAL
		freopen("tunnel2.in","r",stdin);
		#endif
	int n=read();
	G.read(n);T2.read(n);T3.read(n);
	T2.initLca();T3.initLca();
	Divide::work(n);
	writeEN(ans);
	return RET;
}

图论-树分治

WC2018 通道与 CTSC2018 暴力写挂

相关

标签

WC2018 通道 与 CTSC2018 暴力写挂

相关

标签

WC2018 通道与 CTSC2018 暴力写挂