6380. 【NOIP2019模拟2019.10.06】小w与最长路(path)

题目

题目大意

给你一棵树，对于每一条边，求删去这条边之后，再用一条边（自己定）连接两个连通块，形成的树的直径最小是多少。

---

正解

首先，将这棵树的直径给找出来。显然，如果删去的边不在直径上，那么答案就是直径。
接下来考虑删去的边在直径上的情况。
自己连的边应该要是两棵树的直径的中点（中点就是直径上到端点最大距离最小的点）。
答案就是两棵树的直径的一半（当然这是粗略的说法）加上边权，和两棵树内部的直径长度的最大值。
设直径端点为$S$S和$T$T，现在想象直径是横过来的一条线，有一堆树挂在上面。
在直径上从左到右枚举删去哪条边，顺带着维护中点在哪里。
有个结论：中点肯定在原来的直径上。
（后面都以$S$S的一边为例，显然另一边是一样的）
反证法，设中点为$x$x，$x$x不在直径上。设$y$y为$x$x到$S$S路径上第一个出现在直径上的点。
现在找最远的点$z$z。
如果$z$z在$y$y子树之外，那么路径就是$x$x到$y$y和$y$y到$z$z的距离。这时候如果要使$y$y到$z$z最大，则$z=S$z=S。这时候将$x$x变成$y$y更优。
如果$z$z在$x$x子树之内，那么$x$x到$z$z的距离比$x$x到$S$S的距离长，与假设矛盾。
如果$z$z在$y$y子树之内，在$x$x子树之外，那么$y$y到$z$z的距离比$y$y到$S$S的距离长，矛盾。

接下来考虑如何维护直径。
在原来的直径上，对于每个节点，预处理出$f_x$fx​表示$x$x子树中最远点到$x$x的长度。
设$disS_x$disSx​为$x$x到$S$S的距离。
显然，新的直径的一个端点是$S$S。直径可以分成在原来直径上和在某棵子树内的两段。
设$x$x为直径的拐点，则直径的长度为$disS_x+f_x$disSx​+fx​
设$a$a为直径的中点，则直径一半的长度（形象的说法）为$max(disS_a,disS_x+f_x-disS_a)$max(disSa​,disSx​+fx​−disSa​)
现在被删去的边在原来的直径上从左往右移动，每个拐点都能搞出一条路径。在这些路径中找长度最大的，作为直径，然后$a$a移动到$max(disS_a,disS_x+f_x-disS_a)$max(disSa​,disSx​+fx​−disSa​)最小的地方，这时候$a$a就求出来了。
在这个过程中，我们发现$a$a只会从$S$S向$T$T移动。
所以直接$O(n)$O(n)做就可以了（题解说要单调队列，但实际上完全不用。具体见代码。）

---

代码

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2000010
#define ll long long
int n;
struct EDGE{
	int to,w,num;
	EDGE *las;
} e[N*2],*last[N];
int ne;
unsigned long long num;
unsigned long long get(){
	num^=(num<<13);
	num^=(num>>17);
	num^=(num<<5);
	return num;
}
void gen(){
	int B,D;
	scanf("%d%llu%d%d",&n,&num,&B,&D);
	for(int i=2;i<=n;i++){
		int a=get()%min(i-1,B)+i-min(i-1,B),b=get()%D;
		e[ne]={a,b,i-1,last[i]};
		last[i]=e+ne++;
		e[ne]={i,b,i-1,last[a]};
		last[a]=e+ne++;
	}
}
ll ans[N];
int q[N];
ll ds[N],dt[N],alen;
int S,T,pre[N],suc[N];
EDGE *et[N];
void init(){
	static int vis[N];
	int BZ,h,t;
	vis[1]=BZ=1;
	q[h=t=1]=1;
	ll *dis=ds;
	dis[1]=0;
	while (h<=t){
		int x=q[h++],y;
		for (EDGE *ei=last[x];ei;ei=ei->las){
			y=ei->to;
			if (vis[y]!=BZ){
				vis[y]=BZ;
				dis[y]=dis[x]+ei->w;
				q[++t]=y;
			}
		}
	}
	S=1;
	for (int i=1;i<=n;++i)
		if (dis[i]>dis[S])
			S=i;
	q[h=t=1]=S;
	vis[S]=++BZ;
	dis[S]=0;
	while (h<=t){
		int x=q[h++],y;
		for (EDGE *ei=last[x];ei;ei=ei->las){
			y=ei->to;
			if (vis[y]!=BZ){
				vis[y]=BZ;
				dis[y]=dis[x]+ei->w;
				pre[y]=x;
				et[y]=ei;
				q[++t]=y;
			}
		}
	}
	T=S;
	for (int i=1;i<=n;++i)
		if (dis[i]>dis[T])
			T=i;
	for (int i=T;i!=S;i=pre[i])
		suc[pre[i]]=i;
	suc[T]=0;
	for (int i=1;i<=n;++i)
		if (!suc[i] && i!=T)
			pre[i]=0;
}
ll f[N];
int fa[N];
void dp1(int rt){
	int h,t;
	q[h=t=1]=rt;
	fa[rt]=0;
	while (h<=t){
		int x=q[h++],y;
		for (EDGE *ei=last[x];ei;ei=ei->las){
			y=ei->to;
			if (y!=pre[rt] && y!=suc[rt] && y!=fa[x]){
				ans[ei->num]=alen;
				fa[y]=x;
				q[++t]=y;
			}
		}
	}
	for (int i=t;i>=1;--i){
		int x=q[i],y;
		f[x]=0;
		for (EDGE *ei=last[x];ei;ei=ei->las){
			y=ei->to;
			if (y!=pre[rt] && y!=suc[rt] && y!=fa[x])
				f[x]=max(f[x],f[y]+ei->w);
		}
	}
}
ll gs[N],gt[N];
void dp2(int rt,int *cant,ll *g){
	int h,t;
	q[h=t=1]=rt;
	fa[rt]=0;
	while (h<=t){
		int x=q[h++],y;
		for (EDGE *ei=last[x];ei;ei=ei->las){
			y=ei->to;
			if (y!=cant[x] && y!=fa[x]){
				fa[y]=x;
				q[++t]=y;
			}
		}
	}
	for (int i=t;i>=1;--i){
		int x=q[i],y;
		ll fmx=0,smx=0;
		f[x]=0;
		g[x]=0;
		for (EDGE *ei=last[x];ei;ei=ei->las){
			y=ei->to;
			if (y!=cant[x] && y!=fa[x]){
				g[x]=max(g[x],g[y]);
				if (f[y]+ei->w>fmx)
					smx=fmx,fmx=f[y]+ei->w;
				else if (f[y]+ei->w>smx)
					smx=f[y]+ei->w;
			}
		}
		f[x]=fmx;
		g[x]=max(g[x],fmx+smx);
	}
}
ll hs[N],ht[N];
void calc(int beg,int end,int *nxt,ll *h,ll *dis){
	int a=beg,mx=beg;
	h[beg]=f[beg];
	for (int x=nxt[beg];x!=end;x=nxt[x]){
		if (dis[x]+f[x]>dis[mx]+f[mx]){
			mx=x;
			while (a!=x && max(dis[nxt[a]],dis[mx]+f[mx]-dis[nxt[a]])<max(dis[a],dis[mx]+f[mx]-dis[a]))
				a=nxt[a];
		}
		h[x]=max(dis[a],dis[mx]+f[mx]-dis[a]);
	}
}
int main(){
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	gen();
	init();
	alen=ds[T];
	dp2(T,suc,gs),dp2(S,pre,gt);
	for (int i=S;i;i=suc[i])
		dt[i]=alen-ds[i],dp1(i);
	calc(S,T,suc,hs,ds);
	calc(T,S,pre,ht,dt);
	for (int i=S;i!=T;i=suc[i])
		ans[et[suc[i]]->num]=max(max(gs[i],gt[suc[i]]),hs[i]+ht[suc[i]]+et[suc[i]]->w);
	ll s=0;
	for (int i=1;i<n;++i)
		s^=ans[i]%998244353*i%998244353;
	printf("%lld\n",s);
	return 0;
}

---

总结

论猜结论的重要性……