题目

题目大意

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

正解

首先，将这棵树的直径给找出来。显然，如果删去的边不在直径上，那么答案就是直径。

接下来考虑删去的边在直径上的情况。

自己连的边应该要是两棵树的直径的中点（中点就是直径上到端点最大距离最小的点）。

答案就是两棵树的直径的一半（当然这是粗略的说法）加上边权，和两棵树内部的直径长度的最大值。

设直径端点为\(S\)和\(T\)，现在想象直径是横过来的一条线，有一堆树挂在上面。

在直径上从左到右枚举删去哪条边，顺带着维护中点在哪里。

有个结论：中点肯定在原来的直径上。

（后面都以\(S\)的一边为例，显然另一边是一样的）

反证法，设中点为\(x\)，\(x\)不在直径上。设\(y\)为\(x\)到\(S\)路径上第一个出现在直径上的点。

现在找最远的点\(z\)。

如果\(z\)在\(y\)子树之外，那么路径就是\(x\)到\(y\)和\(y\)到\(z\)的距离。这时候如果要使\(y\)到\(z\)最大，则\(z=S\)。这时候将\(x\)变成\(y\)更优。

如果\(z\)在\(x\)子树之内，那么\(x\)到\(z\)的距离比\(x\)到\(S\)的距离长，与假设矛盾。

如果\(z\)在\(y\)子树之内，在\(x\)子树之外，那么\(y\)到\(z\)的距离比\(y\)到\(S\)的距离长，矛盾。

接下来考虑如何维护直径。

在原来的直径上，对于每个节点，预处理出\(f_x\)表示\(x\)子树中最远点到\(x\)的长度。

设\(disS_x\)为\(x\)到\(S\)的距离。

显然，新的直径的一个端点是\(S\)。直径可以分成在原来直径上和在某棵子树内的两段。

设\(x\)为直径的拐点，则直径的长度为\(disS_x+f_x\)

设\(a\)为直径的中点，则直径一半的长度（形象的说法）为\(max(disS_a,disS_x+f_x-disS_a)\)

现在被删去的边在原来的直径上从左往右移动，每个拐点都能搞出一条路径。在这些路径中找长度最大的，作为直径，然后\(a\)移动到\(max(disS_a,disS_x+f_x-disS_a)\)最小的地方，这时候\(a\)就求出来了。

在这个过程中，我们发现\(a\)只会从\(S\)向\(T\)移动。

所以直接\(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;

}

总结

论猜结论的重要性……

巴特西

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

题目

题目大意

正解

代码

总结

最新文章

热门文章