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

Description

• 给一棵带边权的树。
• 对于独立的每条边，首先将其从原来的树上删掉，使这棵树变成两个连通块。
• 然后，将这条边加在这张图的某两个不同节点上，使这两个连通块重新联通。对于每条边，询问怎样将它接回去可以使得新的树最长路径最小，只要求出这个最长路径就好了。
• Hint：操作是临时性的。
• n<=2e6

Solution

• 考虑如果更改非直径的边，因为直径不会改变，所以直接接回原来的地方就好了。
• 有一个十分巧妙的结论：如果更改直径上的边，接回去的两个节点一定在直径上。
• 证明思路：
  对于直径(S,T)，从边(u,v)断开，只用考虑(S,u)，另一半同理。
  求证的是断开后从直径上选择一个点作为起点的最长链的最长链最短。
  假定有一个非直径上的节点更优
  根据从这个点出发的最长链讨论：
  1.出发到直径再沿直径
  2.出发往直径再中途往叶子走
  3.直接往叶子走
  根据这是直径可以发现一些矛盾.（比较抽象）
• 接下来我们只需要考虑，将直径断开之后的一部分，从哪里开始可以使从这个点开始的最长链最小。
• 从直径出发的最长链，要么向直径的端点，要么向反方向到某个点再往非直径的子树中走。
• 为了使这两个的最大值最小，所以要取从端点出发并沿着直径走再往子树走的最长路径，这条路径的中点。
• 枚举断掉的边，只考虑一边相当于不断加点，更新这个最长路径，只会变长，相对应的中点也会单调地移动。
• 把贡献和分开的子树本身的最长链取max就好了。
• 好像讲的不是很清楚。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define max(x,y) ((x>y)?x:y)
#define maxn 2000005
#define mo 998244353
#define ull unsigned long long 
#define ll long long 
using namespace std;

int n,i,j,k;
int em,e[maxn*2],nx[maxn*2],ls[maxn];
ll ec[maxn*2],ans;
struct edge{int x,y,z;} E[maxn];

int B,D; ull num;
ull get(){
	num^=(num<<13),num^=(num>>17),num^=(num<<5);
	return num;
}

void insert(int x,int y,int z){
	em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; ec[em]=z;
	em++; e[em]=x; nx[em]=ls[y]; ls[y]=em; ec[em]=z;
}

ll mxl[maxn],mxlen;
int mxlx[maxn],S,T,fa[maxn],dep[maxn];
void find_chain(int x,int p){
	mxl[x]=0,mxlx[x]=x,fa[x]=p,dep[x]=dep[p]+1;
	for(int i=ls[x];i;i=nx[i]) if (e[i]!=p){
		find_chain(e[i],x);
		if (mxl[x]+mxl[e[i]]+ec[i]>mxlen){
			S=mxlx[x],T=mxlx[e[i]];
			mxlen=mxl[x]+mxl[e[i]]+ec[i];
		}
		if (mxl[e[i]]+ec[i]>mxl[x]) 
			mxl[x]=mxl[e[i]]+ec[i],mxlx[x]=mxlx[e[i]];
	}
}

int dl[maxn],dl0[maxn],dl1[maxn],is[maxn];
void cover_chain(){
	if (dep[S]<dep[T]) swap(S,T);
	int x=S,y=T;
	while (dep[x]>dep[y]) dl0[++dl0[0]]=x,x=fa[x];
	while (x!=y) dl0[++dl0[0]]=x,dl1[++dl1[0]]=y,x=fa[x],y=fa[y];
	for(int i=1;i<=dl0[0];i++) dl[++dl[0]]=dl0[i];
	dl[++dl[0]]=x;
	for(int i=dl1[0];i>=1;i--) dl[++dl[0]]=dl1[i];
	for(int i=1;i<=dl[0];i++) is[dl[i]]=i;
}

ll mx[2][maxn],f[maxn],dis[2][maxn];
void DFS(int x,int p,int t,ll d){
	if (is[x]) dis[t][x]=d; 
	mxl[x]=0;
	for(int i=ls[x];i;i=nx[i]) if (e[i]!=p) {
		DFS(e[i],x,t,d+ec[i]);
		if (is[x]&&!is[e[i]]) f[x]=max(f[x],mxl[e[i]]+ec[i]);
		mx[t][x]=max(mx[t][x],mx[t][e[i]]);
		mx[t][x]=max(mx[t][x],mxl[x]+mxl[e[i]]+ec[i]);
		mxl[x]=max(mxl[x],mxl[e[i]]+ec[i]);
	}
}

int x,y; ll mi[2][maxn],mxdis;
void doit(int t,int i,int d){
	mxdis=max(mxdis,f[dl[i]]+dis[t][dl[i]]);
	while (x!=i&&max(dis[t][dl[x+d]],mxdis-dis[t][dl[x+d]])<max(dis[t][dl[x]],mxdis-dis[t][dl[x]]))
		x+=d;
	mi[t][i]=max(dis[t][dl[x]],mxdis-dis[t][dl[x]]);
}

int main(){
	scanf("%d%llu%d%d",&n,&num,&B,&D);
	for(i=2;i<=n;i++){
		int a=get()%min(i-1,B)+i-min(i-1,B);
		int b=get()%D;
		insert(i,a,b),E[i-1].x=i,E[i-1].y=a,E[i-1].z=b;
	}
	find_chain(1,0);
	cover_chain();
	memset(mxl,0,sizeof(mxl)),DFS(S,0,0,0);
	memset(mxl,0,sizeof(mxl)),DFS(T,0,1,0);
	mi[0][dl[1]]=mxdis=f[dl[1]],x=1;
	for(i=2;i<=dl[0];i++) 
		doit(0,i,1);
	mi[1][dl[dl[0]]]=mxdis=f[dl[dl[0]]],x=dl[0];
	for(i=dl[0]-1;i;i--) 
		doit(1,i,-1);
	ans=0;
	for(i=1;i<n;i++) {
		if (is[E[i].x]==0||is[E[i].y]==0)
			ans^=mxlen%mo*i%mo;
		else {
			x=E[i].x,y=E[i].y;
			if (is[x]>is[y]) swap(x,y);
			ans^=max(max(mx[1][x],mx[0][y]),mi[0][is[x]]+mi[1][is[y]]+E[i].z)%mo*i%mo;
		}
	}
	printf("%lld",ans);
}