lp4332 SHOI2014 三叉神经树

我们知道,每一个\(x_{i}\)各不相同。这启发我们,这一题的点将形成一棵树的结构。
仔细观察题目描述,我们发现,对于每一个点,它的修改影响到的有且仅有它的祖先。
我们不妨设一个点的权值为它的子节点们中信号为1的个数。那么根据题目给出的性质,当且仅当某个节点的权值为1的时候它的某个0子节点变成1,或者某个节点的权值为2的时候它的某个1子节点变成0,这个信号才会继续向上传输。容易发现,这样的传输覆盖的是且总是某一条竖直上下的全1/全2链。
详细地说,如果修改的叶子节点是0变成1,那么影响到的就是从它拉出的一条竖直向上的全1链以及这条链的父亲;如果修改的叶子节点是1变成0,那么影响到的就是从它拉出的一条竖直向上的全2链以及这条链的父亲。
因此,我们可以考虑在LCT剖出的实链上维护全1链以及全2链,然后修改的时候修改一整条链。这就完成了这题的要求。
但是仔细想想,我们会发现,维护全1链和全2链会显得很麻。所以我们不妨改为维护深度最深的非1节点和非2节点。对于将0变为1的操作,我们找到深度最深的非1节点,把它旋到根,然后修改即可,如果深度最深的非1节点不存在,那就意味着根节点也是1,那么答案就会发生变化;对于将1变为0的操作,如法炮制。
另外,由于这一题只有竖直上下的链的操作,所以我们甚至不需要写换根函数。当然,由于这一题没有分离和合并操作,因此,我们也不需要写分离和合并函数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=500005;
int fa[N*3],ch[N*3][2],val[N*3],n1[N*3],n2[N*3],lzy[N*3];
//先看右子节点(下方)是否存在,再看本节点是否满足要求,然后看左子节点(上方)是否存在。 
inline void updt(int X){
	n1[X]=n1[ch[X][1]]?n1[ch[X][1]]:(val[X]==1?n1[ch[X][0]]:X);
	n2[X]=n2[ch[X][1]]?n2[ch[X][1]]:(val[X]==2?n2[ch[X][0]]:X);
}
inline void rnw(int X,int V){
	val[X]^=3,Swap(n1[X],n2[X]),lzy[X]+=V;
}
inline void pshd(int X){
	if(lzy[X]!=0){
		rnw(ch[X][0],lzy[X]);rnw(ch[X][1],lzy[X]);lzy[X]=0;
	}
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N*3];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y];
		st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	} 
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
int n,Q,in[N*3];
std::queue<int> q;
void init(){
	scanf("%d",&n);
	int x,y,z;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d",&x,&y,&z);
		fa[x]=fa[y]=fa[z]=i;
		in[i]=3;
	}
	for(int i=1;i<=(n<<1|1);++i){
		scanf("%d",&x);
		q.push(i+n);
		val[i+n]=x<<1;
	}
	while(!q.empty()){
		x=q.front();
		q.pop();
		if(x<=n){
			updt(x);
		}
		val[fa[x]]+=val[x]>>1;
		--in[fa[x]];
		if(!in[fa[x]]){
			q.push(fa[x]);
		}
	}
	scanf("%d",&Q);
	int tp,nwrt=val[1]>>1;
	for(int i=1;i<=Q;++i){
		scanf("%d",&x);
		tp=(val[x]^=2)-1;
		x=fa[x];
		access(x),splay(x);
		if((~tp?n1:n2)[x]){
			x=(~tp?n1:n2)[x];
			splay(x);
			rnw(ch[x][1],tp),updt(ch[x][1]);
			val[x]+=tp;updt(x);
		}else{
			rnw(x,tp);updt(x);
			nwrt^=1;
		}
		puts(nwrt?"1":"0");
	}
}
int main(){
	init();
	return 0;
}

lp1501 国家集训队 Tree II

如果没有操作2,就是树链剖分套线段树的裸题了。
但是操作2让这题变得麻烦了很多。
考虑LCT。我们知道LCT维护每一条链使用了平衡树。仔细观察这一题的信息,我们发现它们都是可以使用平衡树来维护的。
那么,我们就可以用LCT来维护这道题。
注意:处理信息的时候要先乘再加,否则可能会引起混乱。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define add(X,Y) (X=(X+Y)%MOD)
#define mlt(X,Y) (X=(1ll*X*Y%MOD))
using namespace std;

typedef long long ll;
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=100005;
const ll MOD=51061;
int fa[N],ch[N][2],rev[N],sz[N];
ll sm[N],val[N],lzy1[N],lzy2[N];
inline void updt(int X){
	sz[X]=sz[ch[X][0]]+sz[ch[X][1]]+1;
	sm[X]=(sm[ch[X][0]]+sm[ch[X][1]]+val[X])%MOD;
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void rnw1(int X,ll V){
	add(sm[X],1ll*V*sz[X]);
//	这里不应使用mlt,这是因为mlt会修改原数。 
	add(val[X],V);
	add(lzy1[X],V);
}
inline void rnw2(int X,ll V){
	mlt(sm[X],V);
	mlt(val[X],V);
	mlt(lzy2[X],V);
	mlt(lzy1[X],V);
}
inline void pshd(int X){
	if(lzy2[X]!=1){
		rnw2(ch[X][0],lzy2[X]);
		rnw2(ch[X][1],lzy2[X]);
		lzy2[X]=1;
	}
	if(lzy1[X]){
		rnw1(ch[X][0],lzy1[X]);
		rnw1(ch[X][1],lzy1[X]);
		lzy1[X]=0;
	}
	if(rev[X]){
		if(ch[X][0])flp(ch[X][0]);
		if(ch[X][1])flp(ch[X][1]);
		rev[X]=0;
	}
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[X]=Z,fa[Y]=X;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y],st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline void split(int X,int Y){
	chgrt(X),access(Y),splay(Y);
}
//X在Y下方。
inline void link(int X,int Y){
	chgrt(X),fa[X]=Y;
} 
inline void cut(int X,int Y){
	split(X,Y),fa[X]=ch[Y][0]=0;
}

int n,q;
void init(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		sm[i]=val[i]=lzy2[i]=1;
	}
	int X,Y,P,Q;
	ll V;
	for(int i=1;i<n;++i){
		scanf("%d%d",&X,&Y);
		link(X,Y);
	}
	char op[4];
	for(int i=1;i<=q;++i){
		std::cin>>op;
		scanf("%d%d",&X,&Y);
		switch(op[0]){
			case '+':{
				scanf("%lld",&V);
				split(X,Y);
				rnw1(Y,V);
				break;
			}
			case '-':{
				scanf("%d%d",&P,&Q);
				cut(X,Y);
				link(P,Q);
				break;
			}
			case '*':{
				scanf("%lld",&V);
				split(X,Y);
				rnw2(Y,V);
				break;
			}
			case '/':{
				split(X,Y);
				printf("%lld\n",sm[Y]);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp3203 HNOI2010 弹飞绵羊

依照题意,我们发现,题目求的就是指定点到根的路径长度。
于是,我们对于每一个修改弹力的操作,都可以转化为断边和连边的操作。
那么,我们用Splay维护大小,就可以实现了。
注意:sz数组需要初始化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=200005;
int fa[N],ch[N][2],sz[N];
inline void updt(int X){
	sz[X]=sz[ch[X][0]]+sz[ch[X][1]]+1;
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X;
	while(ntrt(X)){
		Y=fa[X];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	} 
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
//令X在Y的上方。 
//由于这里保证存在有边,所以直接断边即可。 
inline void cut(int X){
	access(X),splay(X);
//	splay(Y);
//	fa[X]=ch[Y][0]=0;
	ch[X][0]=fa[ch[X][0]]=0;
}
inline void link(int X,int Y){
	fa[Y]=X;
	updt(X);
}
int a[N];
int n,q;
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		sz[i]=1;
//		记得初始化sz数组 
		scanf("%d",&a[i]);
		if(i+a[i]<=n){
			link(i+a[i],i);
		}
	}
	scanf("%d",&q);
	int X,Y,op;
	for(int i=1;i<=q;++i){
		scanf("%d",&op);
		if(op==1){
			scanf("%d",&X);++X;
			access(X),splay(X);
			printf("%d\n",sz[X]);
		}else{
			scanf("%d%d",&X,&Y);++X;
			if(X+a[X]<=n){
				cut(X);
			}
			access(X),splay(X);
			if(X+Y<=n){
				link(X+Y,X);
			}
			a[X]=Y;
		}
	}
}
int main(){
//	freopen("3203.in","r",stdin);
//	freopen("3203.myout","w",stdout);
	init();
	return 0;
}

lp2147 SDOI2008 洞穴勘测

维护链接和断开,LCT裸题,(看起来)也可以用按秩合并优化并查集。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>


inline void Swap(int &A,int &B){
	A^=B^=A^=B;
} 
const int N=10005;

int fa[N],ch[N][2],rev[N]; 

inline void updt(int X){
	return;
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void pshd(int X){
	if(rev[X]){
		flp(ch[X][0]),flp(ch[X][1]);
		rev[X]=0;
	}
}
inline int ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline int fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y],st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline int qryrt(int X){
	access(X),splay(X);
	while(ch[X][0]){
		pshd(X);
		X=ch[X][0];
	}
	splay(X);
	return X;
}
inline void split(int X,int Y){
	chgrt(X);
	access(Y),splay(Y);
}
inline bool cut(int X,int Y){
	split(X,Y);
	if(ch[Y][0]!=X||ch[X][1]){
		return 0;
	}
	fa[X]=ch[Y][0]=0;
	return 1;
}
inline bool link(int X,int Y){
	chgrt(X);
	if(qryrt(Y)==X){
		return 0;
	}
	fa[X]=Y;
	return 1;
}
int n,q;
char op[20]; 
void init(){
	scanf("%d%d",&n,&q);
	int x,y;
	for(int i=1;i<=q;++i){
		std::cin>>op;
		scanf("%d%d",&x,&y);
		switch(op[0]){
			case 'C':{
				link(x,y);
				break;
			}
			case 'D':{
				cut(x,y);
				break;
			}
			case 'Q':{
				chgrt(x);
				puts(qryrt(y)==x?"Yes":"No");
				break;
			}
		}
	} 
}
int main(){
	init();
	return 0;
}

lp3690 【模板】Link Cut Tree (动态树)

树链剖分有多种方法。例如以重量为关键字的重链剖分,以长度为关键字的长链剖分。
而LCT(Link-Cut-Tree)就是一种特殊的利用Splay维护树的剖分结构的算法。
我们称一棵树上连接同一条链的边为实边,连接不同的链的边为虚边,那么这棵树就被分成了许多链。我们称这种剖分方法为实链剖分。
由于实链剖分的虚实是可以动态变化的,因此它具有很多用途。比如动态维护连通性、换根等等操作。
下面我们大致地考虑如何用Splay维护LCT实现实链剖分。

对于实链剖分剖出的每一条链,它总是一条自上往下的链。形式化地说,链中的节点的深度连续且各不相同。
对于原树剖分出的每一条链,我们建一棵Splay维护这棵树。每个点在Splay上的权值是这个点在原树上的深度。这样,无论Splay的结构如何改变,这棵Splay始终维护的是一条链。
对于每棵Splay,我们设它的父亲为整个链的最顶端节点的父亲。
对于原树中的一条实边,由于它位于Splay中,所以它对应着Splay中的一组前驱-后继关系。
对于原树中的一条虚边,它连接的两个节点中的一个节点对应的是两条链之间的连接。位于较下方的那条链对应的Splay的父亲显然指向的是位于较上方的那个节点;而位于较上方的那个节点却不必指向位于较下方的那个节点。这条性质被称为「认父不认子」。

access(Y)
显然,在维护信息的时候,原图上的实链结构并不总是能让我们满意。这时候我们需要从根到Y将树上的某一条竖直的链变成实链,并且不改变它原来的性质。这要怎么做呢?
我们设计一个access(接驳)函数,来完成这个过程。
对于路径上的第一条需要变成实边的虚边,我们是容易找到的——这便是Y所在的Splay的根节点连向其父亲的边。当然,这需要我们将Y旋到其所在的Splay的根。
我们将Y所在的Splay的根的父亲A也旋到其所在的Splay的根,那么它原本的实子链在Splay上正好是它的右子树。所以,我们将它的右子节点改为Y节点。那么,A-Y是已经成为了一条满足操作要求的实链,于是问题就转化为了将A-X转化为实链的子问题。
于是依次向上修改即可。

chgrt(X)
在实际操作中,我们操作的链并不总是从某个节点到根的一条链。这时候我们需要换根操作。
首先,我们将根节点到将要成为根的节点X置于同一条实链上——这可以通过access来达成。
在access后,X便是X所在的Splay中原树深度最浅的节点,也就是最右的节点。这时候,倘若将X旋到其所在的Splay的根,然后翻转X,那么整条链就上下倒转了。

qryrt(X)
在确认连通性的时候,我们需要询问某个点X所在的树的根。
显然,这要求的就是access之后X所在的Splay的最左端节点。

split(X,Y)
在处理具体操作的时候,我们可能会需要将某一条链摘离出来。
如果它们连通,只需要换根到一者,然后access另一者即可。

link(X,Y)
从X到Y连边。
方法很简单,将X作为它所在的树的根,然后直接连一条虚边即可。

cut(X,Y)
删除X和Y之间的边。
倘若保证X和Y之间本来是有连边的,那倒是容易了,直接split出来之后分离两者即可。
现在我们需要考虑两者没有连边的情况。
首先,我们将X变为根,然后寻找Y的根。
考虑Splay操作的影响,我们知道,这样操作之后,在Splay树上,Y节点一定在X节点的右儿子的位置。
在这种情况下,如果Y的根不是X,那么显然两者不连通。如果Y不是X的后继,那么显然两者之间有隔着点,也就不是父子关系。

注意:
一:关于Splay:在LCT中,我习惯使用的SplayOne的方法并不是特别有效,这是因为在LCT中存在虚边。
二:在旋转的时候,需要特别注意判断C是空节点和Y是根节点的情况。在这两种情况下有两句话是不应该写的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=300005;
int fa[N],ch[N][2],rev[N],sm[N],val[N];

inline bool isrt(int X){
	return ch[fa[X]][0]!=X&&ch[fa[X]][1]!=X;
}
inline void updt(int X){
	sm[X]=sm[ch[X][0]]^sm[ch[X][1]]^val[X];
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void pshd(int X){
	if(rev[X]){
		if(ch[X][0]){
			flp(ch[X][0]);
		}
		if(ch[X][1]){
			flp(ch[X][1]);
		}
		rev[X]=0;
	}
}
inline int fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
//	int D=fndD(X),D2=fndD(fa[X]);
//	fa[ch[X][D^1]]=fa[X],ch[fa[X]][D]=ch[X][D^1];
//	ch[X][D^1]=fa[X],fa[X]=fa[ch[X][D^1]];
//	ch[fa[X]][D2]=X,fa[ch[X][D^1]]=X;
//	updt(ch[X][D^1]),updt(X);
//	在LCT中,我习惯使用的SplayOne的方法并不是特别有效,这是因为在LCT中存在虚边。
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(fa[X]),C=ch[X][D^1];
	if(!isrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[X]=Z,fa[Y]=X;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(!isrt(Y)){
		Y=fa[Y];
		st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(!isrt(X)){
		Y=fa[X],Z=fa[Y];
		if(!isrt(Y)){
			splayOne((fndD(X)^fndD(Y))?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline int qryrt(int X){
	access(X),splay(X);
	while(ch[X][0]){
		pshd(X);
		X=ch[X][0];
	}
	splay(X);
	return X;
} 
inline void split(int X,int Y){
	chgrt(X);
	access(Y),splay(Y);
} 
inline bool link(int X,int Y){
	chgrt(X);
	if(qryrt(Y)==X){
		return 0;
	}
	fa[X]=Y;
	return 1;
}
inline bool cut(int X,int Y){
	split(X,Y);
	if(ch[Y][0]!=X||ch[X][1]){
		return 0;
	}
	fa[X]=ch[Y][0]=0;
	return 1;
}
int n,q;
void init(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&val[i]);
		sm[i]=val[i];
	}
	int op,x,y;
	for(int i=1;i<=q;++i){
		scanf("%d%d%d",&op,&x,&y);
		switch(op){
			case 0:{
				split(x,y);
				printf("%d\n",sm[y]);
				break;
			}
			case 1:{
				link(x,y);
				break;
			}
			case 2:{
				cut(x,y);
				break;
			}
			case 3:{
				splay(x);
				val[x]=y;
				updt(x);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp3676 小清新数据结构题

仔细考虑这道题,我们可以将问题转化为「修改」和「换根」两个操作。
对于修改操作,我们知道,每个点的权值对且仅对它到根节点上的这一条链上的每个点的答案产生贡献。
我们不妨令以1为根的情况下的每个点的修改前子树权值和为\(a_{i}\),修改对权值的改变为\(dlt\),那么可以计算得:
$$ans’=\sum(a_{i}+dlt)^2=\sum a_{i}^2+2dlt\times a_{i}+dlt^2\times len$$
故而,我们只需要用树链剖分套线段树维护树上区间平方和即可。

接下来我们考虑换根操作。
我们假设根从1换到了\(x\),那么子树权值大小会发生改变的仅有这条路径经过的点。我们不妨令换根后它们的子树权值和为\(b_{i}\),并有1~x为这条路径构成的序列,则我们发现答案会做出如下变动:
$$ans’=ans-\sum_{i=x}^1 a_{i}^2+\sum_{i=x}^1 b_{i}^2$$
我们发现,路径上的相邻点的子树的并集构成了整棵树。这也就意味着:
$$a_{i}+b_{i+1}=a_{0}=b_{x}$$
于是我们可以依此得到:
$$ans’=ans-\sum_{i=x}^1 a_{i}^2+b_x^2+\sum_{i=x-1}^1 (a_{0}-a_{i+1})^2$$
$$ans’=ans-\sum_{i=x}^2 a_{i}^2+(len-1)\times a_{0}^2-2a_{0}\times\sum_{i=x-1}^1 a_{i+1}+\sum_{i=x}^2a_{i}^2$$
$$ans’=(len-1)a_0^2-2a_{0}\sum_{i=x}^2a_{i}$$
同样也可以用树链剖分套线段树维护树上区间和与区间平方和。
注意:树剖不要写挂,下传给重儿子的链顶应该是本节点的链顶。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
typedef long long ll;

inline char rdc() {
 	static char buf[10000000], *p = buf, *end = buf;
	if (p == end) end = buf + fread(p = buf, sizeof(char), 10000000, stdin);
	return *(p++);
}

inline int rd(){
	int RT=0,c,f=1;
	while(!isdigit(c=rdc())){if(c=='-'){f=-1;}}
	do{RT=RT*10+c-'0';}while(isdigit(c=rdc()));
	return RT*f;
}

struct ee{
	int v;
	int nxt;
}e[400005];
int h[200005],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,q;
ll val[200005],sm[200005];
int fa[200005],dep[200005],tp[200005],sn[200005],sz[200005];
int dfn[200005],loc[200005],cnt=0;

inline void dfs0(int X,int FA){
	dep[X]=dep[FA]+1;
	fa[X]=FA;
	sz[X]=1;
	sm[X]=val[X];
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
		sm[X]+=sm[e[i].v];
	}
}

inline void dfs1(int X,int TP){
	loc[dfn[X]=++cnt]=X;
	tp[X]=TP;
	if(sn[X]){
		dfs1(sn[X],TP);
		//这里下传的应该是TP而非X...
		//树剖写挂了,我SB 
	}
	Fv(i,X){
		if(e[i].v==fa[X]||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,e[i].v);
	}
}
#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
struct data{
	ll sm;
	ll sm2;
	ll lzy;
}tr[2000005];

inline void rnw(int X,int Len,ll K){
	tr[X].sm2+=(K*K*Len+tr[X].sm*K*2);
	tr[X].sm+=(Len*K);
	tr[X].lzy+=K;
}
inline void pshd(int X,int L,int R){
	rnw(LS,LLEN,tr[X].lzy),rnw(RS,RLEN,tr[X].lzy);
	tr[X].lzy=0;
}
inline void updt(int X){
	tr[X].sm=tr[LS].sm+tr[RS].sm;
	tr[X].sm2=tr[LS].sm2+tr[RS].sm2;
}
inline void chg(int X,int L,int R,int A,int B,int V){
	if(L>=A&&R<=B){
		rnw(X,LEN,V);
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		chg(LS,L,MID,A,B,V);
	}
	if(B>MID){
		chg(RS,MID+1,R,A,B,V);
	}
	updt(X);
}
inline ll qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm;
	}
	if(L>B||R<A||B<A){
		return 0;
	}
	pshd(X,L,R);
	return qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);
}
inline ll qrySm2(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm2;
	}
	if(L>B||R<A||B<A){
		return 0;
	}
	pshd(X,L,R);
	return qrySm2(LS,L,MID,A,B)+qrySm2(RS,MID+1,R,A,B);
}
inline void build(int X,int L,int R){
	if(L==R){
		tr[X].sm=sm[loc[L]];
		tr[X].sm2=tr[X].sm*tr[X].sm;
		return;
	}
	build(LS,L,MID);build(RS,MID+1,R);
	updt(X);
}

void init(){
	n=rd(),q=rd();
	int u,v;
	for(int i=1;i<n;++i){
		u=rd(),v=rd();
		add(u,v);
	}
	for(int i=1;i<=n;++i){
		val[i]=rd();
	}
	dfs0(1,0);
	dfs1(1,1);
	build(1,1,n);
	int op,x,y;
	ll ans,a0=sm[1],sma,len;
	for(int i=1;i<=q;++i){
		op=rd();
		if(op==1){
			x=rd(),y=rd();
			y-=val[x];
			val[x]+=y;
			a0+=y;
			while(x){
				chg(1,1,n,dfn[tp[x]],dfn[x],y);
				x=fa[tp[x]];
			}
		}else{
			x=rd();
			len=sma=ans=0;
			ans=qrySm2(1,1,n,1,n);
			while(tp[x]!=tp[1]){
				len+=dfn[x]-dfn[tp[x]]+1;
				sma+=qrySm(1,1,n,dfn[tp[x]],dfn[x]);
				x=fa[tp[x]];
			}
			len+=dfn[x]-dfn[1];
			sma+=qrySm(1,1,n,dfn[1]+1,dfn[x]);
			printf("%lld\n",ans+a0*(len*a0-2*sma));
		}
	}
}
int main(){
	init();
	return 0;
}

lp2664 树上游戏

一种\(n^2log^2n\)的做法是可以想到的:点分治,使用multiset来维护以某个节点为根的某一些链上的颜色信息。合并的时候\(O(nlogn)\)合并。
我们略微计算了一下复杂度,感觉这是卡不过去的。

仔细想想我们发现计算一条路径上不同的颜色数量是较为困难的,故而我们可以转而统计不同颜色对\(ans_i\)的贡献。
我们仔细思考,发现,对于以一个点\(rt\)为根的子树的某个点\(i\),其颜色是从\(i\)到\(rt\)的路径上首次出现的,那么我们在计算任意一个其他子树内的点\(j\)答案时,可以将答案减去\(sz_i\),然后再容斥掉\(j\)到\(rt\)路径上存在\(a_i\)这种颜色的情况。
故而,对于每一次分治要处理的以\(rt\)为根的树,我们可以先预处理出\(sm\),表示的是这棵树中所有满足「到根节点路径上没有与其颜色相同的点」的点的子树大小之和;以及\(val_i\),表示的是颜色为\(i\)的到根节点路上没有颜色为\(i\)的节点的子树大小之和。然后我们需要对以它的每一个子节点为根的子树统计答案。
显而易见的,\(j\)到\(rt\)的路径上经过的颜色是不应该被重复统计的,所以我们要让\(sm\)减去\(\sum val_{i}\),其中\(i\)是路径上经过的颜色。
此外,我们还需要统计这些颜色对答案的贡献。令这些颜色的数量为\(nm\),那么它们对\(j\)的答案的贡献就应该是\(nm*dlt\),其中\(dlt\)是\(rt\)除了当前正在找的子节点以外的子节点的子树大小之和。
然后,我们还需要统计以根节点为路径端点的答案数量——这种答案是上述方法未统计到的。所以,我们需要将根节点的答案减去\(val_{a_{rt}}\),然后再加上以根节点为根的所有路径数量,也就是\(sz_{rt}\)

#include<iostream>
#include<cstdio>
#include<set>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)

typedef long long ll;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline ll Max(ll A,ll B){
	return A>B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,a[100005];
int s,rt=0;
int vis[100005];
ll sz[100005],mx[100005],ans[100005];
inline void dfs0(int X,int FA){
	sz[X]=1,mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],s-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
	}
}
ll cnt[100005],val[100005],sm=0,nm=0,dlt;
inline void dfs2(int X,int FA){
	sz[X]=1;
	++cnt[a[X]];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs2(e[i].v,X);
		sz[X]+=sz[e[i].v];
	}
	if(cnt[a[X]]==1){
		sm+=sz[X];
		val[a[X]]+=sz[X];
	}
	--cnt[a[X]];
}
inline void dfs3(int X,int FA,int TYP){
	++cnt[a[X]];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs3(e[i].v,X,TYP);
	}
	if(cnt[a[X]]==1){
		sm+=sz[X]*TYP;
		val[a[X]]+=sz[X]*TYP;
	}
	--cnt[a[X]];
}
inline void dfs4(int X,int FA){
	++cnt[a[X]];
	if(cnt[a[X]]==1){
		++nm;
		sm-=val[a[X]];
	}
	ans[X]+=sm+nm*dlt;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs4(e[i].v,X);
	}
	if(cnt[a[X]]==1){
		--nm;
		sm+=val[a[X]]; 
	}
	--cnt[a[X]];
}
inline void dfs5(int X,int FA){
	val[a[X]]=cnt[a[X]]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs5(e[i].v,X);
	}
}
inline void calc(int X){
	sm=nm=0;
	dfs2(X,0);
	ans[rt]+=sm-val[a[X]]+sz[X];
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		++cnt[a[X]];
		sm-=sz[e[i].v];
		val[a[X]]-=sz[e[i].v];
		dfs3(e[i].v,X,-1);
		--cnt[a[X]];
		
		dlt=sz[X]-sz[e[i].v];
		dfs4(e[i].v,X);
		
		++cnt[a[X]];
		sm+=sz[e[i].v];
		val[a[X]]+=sz[e[i].v]; 
		dfs3(e[i].v,X,1);
		--cnt[a[X]];
	}
	dfs5(X,0);
}

inline void dfs1(int X){
	vis[X]=1;
	calc(X);
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		s=sz[X],rt=0;
		dfs0(e[i].v,X);
		dfs1(rt);
	}
}

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	rt=0,mx[0]=n;
	dfs0(1,0);
	dfs1(rt);
	for(int i=1;i<=n;++i){
		printf("%lld\n",ans[i]);
	}
}

int main(){
	init();
	return 0;
}

lp2634 国家集训队 聪聪可可

这一题本质上和那道「模板 点分治1」是一样的,直接一边统计一边取模即可。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

typedef long long ll;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline ll gcd(ll A,ll B){
	return B?gcd(B,A%B):A;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[40005];
int h[20005],et=0;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et; 
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,W);
}

int n,rt=0,s;
int vis[20005],sz[20005],mx[20005];
inline void dfs0(int X,int FA){
	sz[X]=1,mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],s-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
	}
}
int exist[3],dis[20005],st[20005],st2[20005],tp=0,tp2=0;
ll ans=0;
inline void dfs2(int X,int FA){
	st[++tp]=dis[X];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dis[e[i].v]=dis[X]+e[i].w;
		dfs2(e[i].v,X);
	}
}
inline void calc(int X){
	tp2=0;
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		tp=0;
		dis[e[i].v]=e[i].w;
		dfs2(e[i].v,X);
		for(int j=1;j<=tp;++j){
			ans+=exist[(3-st[j]%3)%3];
		}
		for(int j=1;j<=tp;++j){
			st2[++tp2]=st[j];
			++exist[st[j]%3];
		}
	}
	for(int i=0;i<3;++i){
		exist[i]=0;
	}
}

inline void dfs1(int X){
	exist[0]=vis[X]=1;
	calc(X);
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		rt=0;
		s=sz[X];
		dfs0(e[i].v,X);
		dfs1(rt);
	}
}

void init(){
	scanf("%d",&n);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	} 
	rt=0,mx[0]=n;
	dfs0(1,0);
	dfs1(1);
	ans=(ans<<1)+n;
	ll g=gcd(ans,n*n);
	printf("%lld/%lld\n",ans/g,(n*n)/g);
}

int main(){
	init();
	return 0;
}

lp3806 【模板】点分治1

点分治是一种常常用于处理树上路径统计问题的算法。
首先我们可以想到这一题的一种简单的分治做法:找到一个点,从它开始搜,求出它的每一种长度。然后搜它的每一个子树,找到这些子树的根,求出它们的每一种长度并统计答案。
下面的问题便是要如何统计答案。容易想到的一种方案是枚举以某个点为根的链长两两相加得到的长度再容斥掉重复经过某一条边的路径,也就是所有经过它的同一个子节点的链对。
然而仔细想想这种做法的复杂度是有问题的。在菊花图上,它甚至会达到\(n^2\)的复杂度。故而我们必须另外考虑其他做法。
仔细观察数据范围,我们发现询问个数不超过100,这启发我们考虑一种\(O(nmlogn)\)的做法。
当我们求出以某个节点为根且经过前\(i\)个子节点的所有链以后,我们可以直接标记这这些长度的存在性,然后搜索经过第\(i+1\)个子节点的所有链,并枚举判断询问的长度减去这个链的长度剩下的长度是否存在。
这就做完了。

另:这题的数据是真的水。我犯了两个错,一个是没重设为局部大小,一个是找重心写挂了,而且用的还是复杂度错的算法,居然还过了…

#include<iostream>
#include<cstdio>

#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

inline int Max(int A,int B){
	return A>B?A:B;
}
struct ee{
	int v;
	int w;
	int nxt;
}e[20005];
int h[10005],et=0;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);Eadd(V,U,W);
}
int ans[10005]; 

int n,m,rt,s;

int mx[10005],sz[10005],vis[10005];
inline void dfs0(int X,int FA){
	sz[X]=1,mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],s-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
	}
}
int a[10005];
int dis[10005],tp=0;
inline void dfs2(int X,int FA){
	dis[++tp]=a[X];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		a[e[i].v]=a[X]+e[i].w;
		dfs2(e[i].v,X);
	}
}
int exist[10000005],lst[10005],cnt=0,qry[10005];
inline void calc(int X){
	cnt=0;
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		a[e[i].v]=e[i].w;
		tp=0;
		dfs2(e[i].v,X);
		for(int j=1;j<=m;++j){
			for(int k=1;k<=tp;++k){
				(qry[j]-dis[k]>=0)?ans[j]|=exist[qry[j]-dis[k]]:0; 
			}
		}
		for(int j=1;j<=tp;++j){
			lst[++cnt]=dis[j];
			exist[dis[j]]=1;
		}
	}
	for(int i=1;i<=cnt;++i){
		exist[lst[i]]=0;
	}
}

inline void dfs1(int X){
	exist[0]=vis[X]=1;
	calc(X);
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		s=sz[X],rt=0;//记得重置根。 
		dfs0(e[i].v,X);
		dfs1(rt);
	}
}

void init(){
	scanf("%d%d",&n,&m);
	int u,v,w,x;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		qry[i]=x;
	}
	s=n,mx[0]=n,rt=0;
	dfs0(1,0);
	dfs1(rt);
	for(int i=1;i<=m;++i){
		puts(ans[i]?"AYE":"NAY");
	}
} 

int main(){
	init();
	return 0;
}

lp5175 数列

$$f_{i}=f_{i-1}+a_{i}^2$$
$$a_{i}^2=(xa_{i-1}+ya_{i-2})^2=(x^2a_{i-1}^2+2xya_{i-1}a_{i-2}+y^
2a_{i-2}^2)$$
$$a_{i}a_{i-1}=(xa_{i-1}+ya_{i-2})a_{i-1}=xa_{i-1}^2+ya_{i-1}a_{i-2}$$
故而我们就可以用矩阵加速递推来求这个函数的值。
我们弄出一个如下的基本矩阵:
$$ \left[\begin{matrix}a_{1}^2&a_{2}^2&a_{1}a_{2}&f_{2}\end{matrix}\right]$$
我们不妨将它看作一个四项式,则其中每一项的答案都可以从上述公式推得。故而可以得到这样一个矩阵:
$$ \left[\begin{matrix}0&y^2&0&y^2\\1&x^2&x&x^2\\0&2xy&y&2xy\\0&0&0&1\end{matrix}\right]$$
拿来矩阵快速幂一下即可。

#include<iostream>
#include<cstdio>


typedef long long ll;
const ll MOD=1000000007;

struct Mat{
	ll a[4][4];
	inline void init(){
		for(int i=0;i<4;++i){
			for(int j=0;j<4;++j){
				a[i][j]=0;
			}
		}
	}
	inline Mat operator*(const Mat &B)const{
		Mat C;
		C.init();
		for(int i=0;i<4;++i){
			for(int j=0;j<4;++j){
				for(int k=0;k<4;++k){
					C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%MOD;
				}
			}
		}
		return C;
	}
};
ll a1,a2,n,x,y;
void init(){
	scanf("%lld%lld%lld%lld%lld",&n,&a1,&a2,&x,&y);
	if(n==1){
		printf("%lld\n",a1*a1%MOD);
		return;
	}
	if(n==2){
		printf("%lld\n",(a2*a2+a1*a1)%MOD);
	}
	Mat BS,T;
	BS.init(),T.init();
	BS.a[0][0]=a1*a1%MOD,BS.a[0][1]=a2*a2%MOD,BS.a[0][2]=a1*a2%MOD,BS.a[0][3]=(BS.a[0][0]+BS.a[0][1])%MOD;
	T.a[0][0]=0,T.a[0][1]=y*y%MOD,T.a[0][2]=0,T.a[0][3]=y*y%MOD;
	T.a[1][0]=1,T.a[1][1]=x*x%MOD,T.a[1][2]=x,T.a[1][3]=x*x%MOD;
	T.a[2][0]=0,T.a[2][1]=2*x*y%MOD,T.a[2][2]=y,T.a[2][3]=2*x*y%MOD;
	T.a[3][0]=0,T.a[3][1]=0,T.a[3][2]=0,T.a[3][3]=1;
	n-=2;
	while(n){
		if(n&1){
			BS=BS*T;
		}
		T=T*T;
		n>>=1;
	}
	printf("%lld\n",BS.a[0][3]);
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

lp5236 【模板】静态仙人掌(圆方树)

按照我们之前的经验,仙人掌上问题往往可以通过圆方树转化为树上问题。
我们发现,最短路在树上是一种非常容易解决的问题。只需预处理到根节点的长度然后死命跑LCA就可以了。
但是在一般图上,最短路的实时处理就会变得很困难。
我们可以尝试通过给圆方树上的边赋上特别的边权来处理这个问题。

对于圆-圆边,赋边权为原边权,这是容易理解的。
对于方点到它的父亲圆点的边,赋边权为0,对于圆点到它的父亲方点的边,赋边权为这个圆点到这个方点的父亲圆点的最短距离。

这时候我们会遇到一个问题,就是Tarjan找环的时候找不到返祖边的边权。
解决方案是记录每一个到根节点在dfs树上的距离,然后当我们找到一个环一路找爸爸并统计长度即可。

然后是计算答案,我们发现,如果询问的两个点的最近公共祖先是一个方点,那么它们的答案不能用普通方法计算。
我一开始的想法是尝试直接用某个节点到父亲方点的边权直接计算答案,但这样会导致答案错误,原因是它无法正确地区分两个点位于圆环的同一侧还是不同侧的情况。
故而,我们需要保存原来的距离它的父亲方点的靠某一侧的距离,故而当lca是方点的时候特殊判断计算即可。

 #include<iostream>
#include<cstdio>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

typedef long long ll;

inline ll Min(ll A,ll B){
    return A<B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
inline ll Abs(ll A){
	return A>0?A:-A;
}
inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}

struct ee{
    int v;
    ll w;
    int nxt;
}e[200005];
int h0[10005],h[20005],et=0;
inline void Eadd(int *H,int U,int V,ll W){
    e[++et]=(ee){V,W,H[U]};
    H[U]=et;
}
inline void add(int *H,int U,int V,ll W){
    Eadd(H,U,V,W);
    Eadd(H,V,U,W);
}
int dfn[20005],lw[20005],cnt=0,dep[20005],fa[20005][30];
ll dis[20005],sz[20005];
int nm=0;
int st[20005],tp=0;
inline void dfs0(int X){
    dfn[X]=lw[X]=++cnt;
    Fv(h0,i,X){
    	if(e[i].v==fa[X][0]){
    		continue;
		}
        if(!dfn[e[i].v]){
            fa[e[i].v][0]=X;
            dis[e[i].v]=dis[X]+e[i].w;
            dfs0(e[i].v);
            lw[X]=Min(lw[X],lw[e[i].v]);
    	}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
			if(e[i].v!=fa[X][0]&&dfn[e[i].v]<dfn[X]){
                ++nm;
                add(h,nm,e[i].v,0);
                ll len=e[i].w;
                for(int j=X;j^e[i].v;j=fa[j][0]){
                	len+=dis[j]-dis[fa[j][0]];
                }
                sz[nm]=len;
                ll nw=e[i].w;
                for(int j=X;j^e[i].v;j=fa[j][0]){
                    add(h,nm,j,Min(nw,len-nw));
                    sz[j]=nw; 
                    nw+=dis[j]-dis[fa[j][0]];
                }
            }
        }
        if(lw[e[i].v]>dfn[X]){
        	add(h,X,e[i].v,e[i].w);
		} 
    }
}

inline void dfs1(int X,int FA){
    dep[X]=dep[FA]+1;
    fa[X][0]=FA;
    Fv(h,i,X){
        if(e[i].v!=FA){
            dis[e[i].v]=dis[X]+e[i].w;
            dfs1(e[i].v,X);
        }
    }
}

int n,m,q;

inline ll calc(int X,int Y){
    int XX=X,YY=Y,lca;
    while(dep[XX]<dep[YY]){
        Swap(XX,YY);
    }
    for(int i=20;~i;--i){
        if(dep[XX]-(1<<i)>=dep[YY]){
            XX=fa[XX][i];
        }
    }
    if(XX==YY){
        lca=XX;
    }else{
        for(int i=20;~i;--i){
            if(fa[XX][i]!=fa[YY][i]){
                XX=fa[XX][i];
                YY=fa[YY][i];
            }
        }
        lca=fa[XX][0];
    }
    ll RT=dis[X]+dis[Y]-(dis[lca]<<1);
    if(lca>n){
        ll P=dis[XX]-dis[lca],Q=dis[YY]-dis[lca];
        RT-=(P+Q);
        RT+=Min(sz[lca]-Abs(sz[XX]-sz[YY]),Abs(sz[XX]-sz[YY]));
    }
    return RT;
}



void init(){
    scanf("%d%d%d",&n,&m,&q);
    nm=n;
    int u,v;
	ll w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%lld",&u,&v,&w);
        add(h0,u,v,w);
    }
    fa[1][0]=0;
    dfs0(1);
    for(int i=1;i<=nm;++i){
        dep[i]=0,dis[i]=0;
    }
    dfs1(1,0);
    for(int j=1;j<=20;++j){
        for(int i=1;i<=nm;++i){
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
    int x,y;
    for(int i=1;i<=q;++i){
        scanf("%d%d",&x,&y);
        printf("%lld\n",calc(x,y));
    }
}
int main(){
    init();
    return 0;
}

lp3320 SDOI2015 寻宝游戏

我们找到了这样一个结论:
「一个树上点集构成的最小生成树中,若两点间有路径,则此两点的DFS序在树上相近。」
这个结论的证明是较为困难的,但是感性理解还是比较容易的。
有了这个结论,我们就可以解决这一题。
每当一个新的点x即将加入点集的时候,我们只需要计算点集中DFS序刚好比它小的点y和DFS序刚好比它大的点z,然后将答案加上如下的式子:
$$dis_{x,y}+dis_{x,z}-dis_{y,z}$$
删去的时候逆向操作即可。
维护点集可以使用set。(善用STL(大雾))计算路径长度可以LCA+容斥。

注意:记得开long long

#include<iostream>
#include<cstdio>
#include<set>

struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
int fa[100005][30],dfn[100005],loc[100005],dep[100005],cnt=0;
long long val[100005];
//注意将两种深度分开。 
inline void dfs(int X,int FA){
	fa[X][0]=FA,dfn[X]=++cnt,loc[cnt]=X,dep[X]=dep[FA]+1;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			val[e[i].v]=val[X]+e[i].w;
			dfs(e[i].v,X);
		}
	}
}

inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		std::swap(X,Y);
	}
	for(int i=20;i>=0;--i){
		if(dep[X]-(1<<i)>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=20;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i];
			Y=fa[Y][i];
		}
	}
	return fa[X][0];
}

inline long long dis(int X,int Y){
	return val[X]+val[Y]-(val[lca(X,Y)]<<1);
}

int n,m;
long long ans=0;
bool vis[100005];
std::set<int> s;
void init(){
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,0);
	for(int j=1;j<=20;++j){
		for(int i=1;i<=n;++i){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	int x,y,z;
	long long d;
	std::set<int>::iterator it;
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		x=dfn[x];
		if(!vis[loc[x]]){
			s.insert(x);
		}
		y=loc[(it=s.lower_bound(x))==s.begin()?*--s.end():*--it];
		z=loc[(it=s.upper_bound(x))==s.end()?*s.begin():*it];
		//注意运算符优先级。 
		if(vis[loc[x]]){
			s.erase(x);
		}
		x=loc[x];
		d=dis(x,y)+dis(x,z)-dis(y,z);
		if(!vis[x]){
			vis[x]=1;
			ans+=d;
		}else{
			vis[x]=0;
			ans-=d;
		}
		//注意前后的x不是一个x 
		printf("%lld\n",ans);
	}
}

int main(){
	init();
	return 0;
}

CF487E Tourists

众所周知,圆方树是用来处理图上点双相关问题的。
同时,点双又是一个和简单路径密切相关的东西。故而这一题我们可以考虑用圆方树来处理。
我们发现,如果两点之间有多条简单路径,那么它们一定处于同一个点双中。所以,我们可以把原图转化为圆方树,这样就可以用树链剖分套线段树来求解询问了。
但是题目要求要修改点权,这要怎么办呢?

一个直观的想法是暴力修改每个点周围相邻的方点。然而事实上如果出现了个菊花套菊花套菊花图的话显然是会严重TLE的。
我们考虑一种动态维护一个方点的点值的算法。我们尝试对每个方点开一个mulitiset,每当修改一个点的点权的时候就把旧的点权删去然后插入新的点权,并更新方点点值。
然而,如果每个修改的圆点周围都有很多的方点的话,这种做法仍然有TLE的风险。我们考虑对于每个圆点,只更新它的父亲方点。
它对它的儿子方点的贡献,则在询问的时候统计。
这样复杂度就对了。
这就使用了圆方树上树链剖分套线段树解决了这道题。

注意:
树链剖分中更新最大孩子的部分,这里是son!不是sz!调了我一个晚上!

#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<set>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

std::multiset<int> s[200005]; 

const int INF=2147483647;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}

struct ee{
	int v;
	int nxt;
}e[2000005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int *H,int U,int V){
	Eadd(H,U,V);
	Eadd(H,V,U);
}


int dfn[200005],lw[100005];
//注意数组大小。 
int nm,cnt=0;
int st[100005],tp=0;
inline void dfs0(int X){
	dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	Fv(h0,i,X){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);
			lw[X]=Min(lw[X],lw[e[i].v]);
			if(lw[e[i].v]==dfn[X]){
				++nm;
				for(int j=0;j!=e[i].v;--tp){
					j=st[tp];
					add(h,nm,j);
				}
				add(h,X,nm);
			}
		}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
}
int fa[200005],sz[200005],dep[200005],son[200005],top[200005],loc[200005];
inline void dfs1(int X,int FA){
	fa[X]=FA,dep[X]=dep[FA]+1,sz[X]=1;
	Fv(h,i,X){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
			sz[X]+=sz[e[i].v];
			if(sz[son[X]]<sz[e[i].v]){
				son[X]=e[i].v;
				//这里是son!不是sz!调了我一个晚上! 
			}
		}
	}
}
inline void dfs2(int X,int FA,int TP){
	dfn[X]=++cnt,loc[cnt]=X,top[X]=TP;
	if(son[X]){
		dfs2(son[X],X,TP);
	}
	Fv(h,i,X){
		if(e[i].v!=FA&&e[i].v!=son[X]){
			dfs2(e[i].v,X,e[i].v);
		}
	}
}

int n,m,q;
int a[200005];

#define MID (L+R>>1)
#define LS (X<<1)
#define RS (X<<1|1)

int tr[600005];
inline void bld(int X,int L,int R){
	if(L==R){
		tr[X]=a[loc[L]];
//		记得逆哈希 
		return;
	}
	bld(LS,L,MID);
	bld(RS,MID+1,R);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline void chg(int X,int L,int R,int P,int V){
	if(L==R){
		tr[X]=V;
		return;
	}
	P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline int qry(int X,int L,int R,int A,int B){
	if(A>R||L>B){
		return INF;
	}
	if(A<=L&&R<=B){
		return tr[X];
	}
	return Min(qry(LS,L,MID,A,B),qry(RS,MID+1,R,A,B));
}

void init(){
	scanf("%d%d%d",&n,&m,&q);
	nm=n;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(h0,u,v);
	}
	dfs0(1);
	dfs1(1,0);
	cnt=0;
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		if(fa[i]){
			s[fa[i]].insert(a[i]);
		}
	}
	for(int i=n+1;i<=nm;++i){
		a[i]=*s[i].begin();
	}
	
	bld(1,1,nm);
	char ch[3];
	int x,y;
	int ans;
	
	for(int i=1;i<=q;++i){
		scanf("%s%d%d",ch,&x,&y);
		if(ch[0]=='C'){
			chg(1,1,nm,dfn[x],y);
			if(fa[x]){
				u=fa[x];
				s[u].erase(s[u].lower_bound(a[x]));
				s[u].insert(y);
				if(a[u]!=*s[u].begin()){
					a[u]=*s[u].begin();
					chg(1,1,nm,dfn[u],a[u]);
				}
			}
			a[x]=y;
		}else{
			ans=INF;
			while(top[x]!=top[y]){
				if(dep[top[x]]<dep[top[y]]){
					Swap(x,y);
				}
				ans=Min(ans,qry(1,1,nm,dfn[top[x]],dfn[x]));
				x=fa[top[x]];
			}
			if(dfn[x]>dfn[y]){
				Swap(x,y);
			}
			ans=Min(ans,qry(1,1,nm,dfn[x],dfn[y]));
			if(x>n){
				ans=Min(ans,a[fa[x]]);
			}
			printf("%d\n",ans);
		}
	} 
}

int main(){
	init();
	return 0;
}

lp4630 APIO2018 Duathlon 铁人两项

圆方树是一种在仙人掌图上常用的数据结构,但是这并不意味着圆方树只在仙人掌图上有用。事实上,在任何一张图上,我们都可以用相似的方法来构造一棵圆方树。
对于一张图,我们预处理出它的所有点双,然后对每一个点双建一个方点,其他处理方法和仙人掌上圆方树几乎相同。
这里的点双要如何预处理呢?我们考虑一个性质:当我们预处理出一张图的DFS树后,任何一条边属于且仅属于一个点双。
那么,我们就可以尝试找到一个点双中深度最浅的节点,然后由它构造出这个方点。
我们发现,当我们搜索完一个节点的子树后,如果子节点中的某一个节点的lw是这个节点,那么这个节点就是它所在的点双中深度最浅的节点。
这是因为,如果一个节点的lw节点是它的父节点,那么它和它的子树就没有任何返祖边能够到达比当前节点更浅的节点,也就说明如果当前节点在点双内,那么它一定是点双内最浅的节点。
有没有可能当前节点不在点双内呢?这是不可能的。如果有返祖边连向当前节点,那么当前节点显然不会成为割点;如果没有,那么当前节点所属的点双就一定只有两个点。

现在把目光投到这道题。
首先考虑点双的基本性质。我们发现,对于至少有三个点的点双,任取三个点,它们总是一对满足题意的三元组。
这是由于点双的定义,点双里没有割点,自然总是可以找到两点间的两条不相交的简单路径。
拓展这个结论,我们发现,如果一条简单路径经过一个点双,那么显然无论固定哪个点,这条路径都始终是一条简单路径。
故而,对于选定的起点和终点,我们可以分两类讨论。
倘若它们位于同一个点双,那么显然它们之间的满足题意的三元组个数恰好是这个点双的点数-2
对于不属于同一个点双的情况,它们之间有可能经过其他的点双,也有可能不经过。每经过一个点双,它们之间的满足题意的三元组个数就会加上这个点双的点的个数。
同时,答案还要加上起点和终点各自处在的点双的点数个数各自-1。
这要怎么统计呢?我们可以让每个方点的权值为点双中的点的数量,每个圆点的权值为-1,然后枚举点对统计路径和即可。
仔细一想觉得有点不对劲儿:这样的复杂度岂不是要n^2logn级别?妥妥地T啊。
正难则反,我们可以统计每个点对答案的贡献,也就是经过它的路径数乘上它本身的权值。而前者可以通过一个普通的树形DP求得。
这就做完了。

注意:
要注意每个点的子树外的节点的数量是相当于连通块大小减去它的子树大小,而非总节点数减去它的子树大小。故而要注意统计连通块大小。

#include<iostream>
#include<cstdio>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[1200005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int *H,int U,int V){
	Eadd(H,U,V);
	Eadd(H,V,U);
}

int n,m;
int dfn[100005],lw[100005],cnt=0,nm=0;
int st[100005],tp=0;
int val[200005],nwsz;
long long ans=0;
inline void dfs(int X){
	dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	++nwsz;
//	要注意每个点的子树外的节点的数量是相当于连通块大小减去它的子树大小,而非总节点数减去它的子树大小。故而要注意统计连通块大小。 
	Fv(h0,i,X){
		if(!dfn[e[i].v]){
			dfs(e[i].v);
			lw[X]=Min(lw[X],lw[e[i].v]);
			if(lw[e[i].v]==dfn[X]){
//				注意这里应当判定的是lw(v)=dfn(u) 
				val[++nm]=1;
				for(int j=0;j!=e[i].v;--tp){
					++val[nm];
					j=st[tp];
					add(h,nm,j);
				}
				add(h,X,nm);
			}
		}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
}

int vis[200005],sz[200005];

inline void dfs2(int X){
	vis[X]=1;
	sz[X]=(X<=n);
	Fv(h,i,X){
		if(!vis[e[i].v]){
			dfs2(e[i].v);
			ans+=2ll*val[X]*sz[X]*sz[e[i].v];
			sz[X]+=sz[e[i].v];
		}
	}
	ans+=2ll*val[X]*sz[X]*(nwsz-sz[X]);
}

void init(){
	scanf("%d%d",&n,&m);
	nm=n;
	for(int i=1;i<=n;++i){
		val[i]=-1;
	}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(h0,u,v);
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			nwsz=0;
			dfs(i);
			dfs2(i);
			--tp;
		}
	}
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}

lp4244 SHOI2008 仙人掌图 II

仙人掌图是每一个点双都只有一个环的连通图。
对于一个仙人掌图,它在许多方面都有树的性质,只是其中的有一些节点被换成了环。
我们不妨依然采用一种伪树形DP的方式来处理这棵树,我们发现,非环节点的转移都是非常容易达成了,问题在于环上的节点的转移。

首先,我们要找到这个环,这可以用Tarjan算法来完成。
具体来说,我们维护两个数组:dfn和lw,其中前者表示的是某一个节点的dfs序,后者表示的是某一个节点至多走一条返祖边或者父亲边能够到达的最小dfs序。
显然,在搜索中,如果下一个节点未被访问过,我们就可以在搜索完它以后将当前节点的lw与它的lw取较小值。
否则,当前节点通向它的边一定是一条返祖边或者父亲边,那么当前节点的lw值应当与它的dfs序取较小值。

对于一个环,我们如果将它视为一个节点,我们想一想要怎么从它的「孩子」们处转移呢?
我们发现,依次枚举它的每一个孩子,答案显然是:
$$max(f_i+f_j+dis_{i,j})$$
这个式子可以使用单调队列优化。所以我们每一次把一个环提出来瞎DP一下就好了。

#include<iostream>
#include<cstdio>
#include<deque>
#define Fv(A,U) for(int A=h[U];A;A=e[A].nxt)

inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[200005];
int et=0,h[100005];
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,m;
int dfn[100005],lw[100005],dep[100005],fa[100005],cnt=0;
int ans=0,f[100005],a[100005];
std::deque<int> q;
inline void calc(int X,int Y){
	int tot=dep[Y]-dep[X]+1;
	int nw=tot;
	for(int i=Y;i!=X;i=fa[i]){
		a[nw--]=f[i];
	}
	a[nw]=f[X];
	for(int i=1;i<=tot;++i){
		a[tot+i]=a[i];
	}
	while(!q.empty()){
		q.pop_front();
	}
	q.push_back(1);
	for(int i=2;i<=(tot<<1);++i){
		while(!q.empty()&&i-q.front()>(tot>>1)){
			q.pop_front();
		}
		if(!q.empty()){
			ans=Max(ans,a[i]+a[q.front()]+i-q.front());
		}
		while(!q.empty()&&a[q.back()]-q.back()<a[i]-i){
			q.pop_back();
		}
		q.push_back(i);
	}
	for(int i=2;i<=tot;++i){
		f[X]=Max(f[X],a[i]+Min(i-1,tot-i+1));
	}
}
inline void dfs(int X,int FA){
	dfn[X]=lw[X]=++cnt;
	Fv(i,X){
		if(e[i].v!=FA){//这一句如果不加会无形降低很多点的lw值,从而使环的大小变成0。 
			if(!dfn[e[i].v]){
				fa[e[i].v]=X;
				dep[e[i].v]=dep[X]+1;
				dfs(e[i].v,X);
				lw[X]=Min(lw[X],lw[e[i].v]);
			}else{
				lw[X]=Min(lw[X],dfn[e[i].v]);
			}
			if(lw[e[i].v]>dfn[X]){
				ans=Max(ans,f[X]+f[e[i].v]+1);
				f[X]=Max(f[X],f[e[i].v]+1);
			}
		}
		
	}
	Fv(i,X){
		if(fa[e[i].v]!=X&&dfn[X]<dfn[e[i].v]){
			calc(X,e[i].v);
		}
	}
}

void init(){
	scanf("%d%d",&n,&m);
	int u,v,x;
	for(int i=1;i<=m;++i){
		u=0;
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d",&v);
			if(u){
				add(u,v);
			}
			u=v;
		}
	}
	dfs(1,0);
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

CF1138

这么早的CF已经很少见了。


CF1138A
是的这题调了我半个小时。
别说了,丢人。
具体来说就是我写代码的时候默认nw总是较小的那个,但事实上有时候a[i]也有可能是较小的那个。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int a[1000005],b[1000005];
int n;

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&b[i]);
	}
	a[1]=1;
	int nw=0,ans=0;
	for(int i=2;i<=n;++i){
		if(b[i]!=b[i-1]){
			nw=a[i-1];
			a[i]=1;
			ans=max(ans,min(nw,a[i]));
		}else{
			a[i]=a[i-1]+1;
			ans=max(ans,min(nw,a[i]));
		}
	}
	printf("%d\n",ans*2);
}
int main(){
	init();
	return 0;
}


CF1138B
这题我是松过去的。
一开始没看数据范围还有O(n)的幻想,看了以后就开始YY平方级的做法,但是编了半天没编出来。
最后决定破釜沉舟,写一个复杂度三方不满的暴力,居然一发入魂过了。Amazing!
一开始觉得复杂度是十亿左右,现在仔细算一算应该是一亿出头,加上常数小卡过去其实确实是有可能的。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
char a[5005],b[5005];
int val[5005];
int mp[5005][5005];
bool vis[5005];
inline void prnt(int i,int j,int k,int l){
	int i1=0,j1=0,k1=0,l1=0;
	for(int t=1;t<=n;++t){
		if(val[t]==0&&i1<i){
			++i1;
			printf("%d ",t);
		}
		if(val[t]==1&&k1<k){
			++k1;
			printf("%d ",t);
		}
		if(val[t]==2&&j1<j){
			++j1;
			printf("%d ",t);
		}
		if(val[t]==3&&l1<l){
			++l1;
			printf("%d ",t);
		}
	}
}
void init(){
	scanf("%d",&n);
	cin>>a+1>>b+1;
	int q=0,w=0,e=0,r=0;
	for(int i=1;i<=n;++i){
		if(a[i]=='0'&&b[i]=='0'){
			++q;
			val[i]=0;
		}
		if(a[i]=='1'&&b[i]=='0'){
			++w;
			val[i]=1;
		}
		if(a[i]=='0'&&b[i]=='1'){
			++e;
			val[i]=2;
		}
		if(a[i]=='1'&&b[i]=='1'){
			++r;
			val[i]=3;
		}
	}
//	fst->w,scn->e
	for(int i=0;i<=min(n/2,q);++i){
		for(int j=0;j<=min(n/2-i,e);++j){
			for(int k=0;k<=min(n/2-i-j,w);++k){
				int l=n/2-i-j-k;
				if(l>r){
					continue;
				}
				if(i+k==e-j+q-i&&j+l==w-k+r-l){
					prnt(q-i,e-j,w-k,r-l);
					return;
				}
			}
		}
	}
	puts("-1");
	return;
}
int main(){
	init();
	return 0;
}


CF1138C
看到这题首先就可以想到离散化。
具体来说就是我们对于每一行和每一列都各自离散化,然后计算出每个格子在这一行/列的相对大小。
由于大小关系不能改变,所以这个相对大小必须取较大值,这样才能留下足够的空间。
同样的,比每个格子大的数量也要取较大值,也是为了留下足够的空间。
然后就可以了。
不过我离散化写丑了,丢人。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n,m;
int a[1005][1005],a1[1005][1005],a2[1005][1005];
int b[1005];
int mx1[1005],mx2[1005];
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
		}
	}
	int nw;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			b[j]=a[i][j];
		}
		sort(b+1,b+1+m);
		mx1[i]=unique(b+1,b+m+1)-b-1;
		for(int j=1;j<=m;++j){
			a1[i][j]=lower_bound(b+1,b+mx1[i]+1,a[i][j])-b;
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			b[j]=a[j][i]; 
		}
		sort(b+1,b+1+n);
		mx2[i]=unique(b+1,b+n+1)-b-1;
		for(int j=1;j<=n;++j){
			a2[j][i]=lower_bound(b+1,b+mx2[i]+1,a[j][i])-b;
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			printf("%d ",max(a1[i][j],a2[i][j])+max(mx1[i]-a1[i][j],mx2[j]-a2[i][j]));
		}
		puts("");
	}
}
int main(){
	init();
	return 0;
}


CF1138D
第一个想法是暴力循环,但是那样子好像会WA9。
仔细考虑一下发现需要处理出最大非本身Border,然后分两段乱搞。
当然是要上一个KMP了。
但是我乱搞还是写丑了,WA在几十个点。现在想来应该是输出剩余的东西的时候写得丑了。最后参考了小粉兔的才通过。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

char a[500005],b[500005];
int x,y,n,m;
int nxt[500005];
void init(){
	cin>>a+1;
	cin>>b+1;
	n=strlen(a+1);
	m=strlen(b+1);
	for(int i=1;i<=n;++i){
		if(a[i]=='1'){
			++x;
		}else{
			++y;
		}
	}
	int l1;
	int j=0;
    for(int i=2;i<=m;i++){
        while(j&&(b[i]!=b[j+1])){
            j=nxt[j];
        }
        if(b[j+1]==b[i]){
            j++;
        }
        nxt[i]=j;
    }
    l1=nxt[m];
	j=0;
    for(int i=1;i<=n;++i){
    	if(b[j+1]=='1'&&x){
    		putchar('1');
    		--x;++j;
    		if(j==m){
    			j=l1;
			}
		}else if(b[j+1]=='0'&&y){
			putchar('0');
			--y;++j;
			if(j==m){
				j=l1;
			}
		}else{
			putchar(b[j+1]=='0'?'1':'0');
		}
	}
}
int main(){
	init();
	return 0;
}

lp4382 八省联考2018 劈配

扫一眼题目,看到n个点和m个点匹配的问题,你就会有一种预感——是不是要跑二分图匹配?
是的,就是要跑二分图匹配。
第一问很显然,大力让一个导师能够被多个学生匹配,然后跑一个类似于匈牙利的操作。然后如果匹配满了,我们就考虑将这个导师匹配的其他学生尝试匹配同一个优先级的其他节点。
这个复杂度肯定是很松的。
那么关键在于第二问要怎么处理。
观察发现答案具有单调性。也就是说,如果一个选手在较高的优先度会感到沮丧,那么他在一个较低的优先度也会感到沮丧;
因此我们考虑二分答案来检验。
这样的复杂度大概是三方乘对数级的。时间比较紧张。
我们考虑一种优化策略:发现选手提高到某个优先度了以后,他就相当于顶替了本来在这个优先度的选手的位置。
故而,我们可以对于前缀的选手,储存到每个选手时的匹配状态。每次找到某个优先度,就把他的信息加入到对应的匹配状态中,然后跑上述操作。
这样可以优化到平方乘对数级,可能可以通过此题。
这一题的具体操作——也就是那个一点多匹配的操作并不是特别会,以后需要重新研究。
我好菜啊。

#include<iostream>
#include<cstdio>

int c,n,m;
int mx[205],a[205][205],val[205][205][15],exp[205];
int usd[205],usd1[205],usd2[205][205],vis[205];
int prusd[205][205],prusd1[205][205],prusd2[205][205][205];
inline bool dfs(int X,int V){
	int nw,nxt;
	for(int i=1;i<=val[X][V][0];++i){
		nw=val[X][V][i];
		if(vis[nw]){
			continue;
		}
		vis[nw]=1;
		if(usd[nw]<mx[nw]){
			usd1[X]=nw;
			usd2[nw][++usd[nw]]=X;
			return 1;
		}
		for(int j=1;j<=mx[nw];++j){
			nxt=usd2[nw][j];
			if(dfs(nxt,a[nxt][nw])){
				usd1[X]=nw;
				usd2[nw][j]=X;
				return 1;
			}
		}
	}
	return 0;
}
inline void calc1(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[j]=0;
		}
		for(int j=1;j<=m;++j){
			if(!val[i][j][0]){
				continue;
			}
			if(dfs(i,j)){
				break;
			}
		}
		for(int j=1;j<=m;++j){
			prusd[i][j]=usd[j];
		}
		for(int j=1;j<=i;++j){
			prusd1[i][j]=usd1[j];
		}
		for(int j=1;j<=m;++j){
			for(int k=1;k<=usd[j];++k){
				prusd2[i][j][k]=usd2[j][k];
			}
		}
	}
}
inline bool chck(int X,int Y){
	for(int i=1;i<=m;++i){
		usd[i]=prusd[Y-1][i];
	}
	for(int i=1;i<=Y-1;++i){
		usd1[i]=prusd1[Y-1][i];
	}
	for(int i=1;i<=m;++i){
		for(int j=1;j<=usd[i];++j){
			usd2[i][j]=prusd2[Y-1][i][j];
		}
	}
	for(int i=1;i<=m;++i){
		vis[i]=0;
	}
	for(int i=1;i<=exp[X];++i){
		if(!val[X][i][0]){
			continue;
		}
		if(dfs(X,i)){
			return 1;
		}
	}
	return 0;
}
void init(){
//	注意清空数组!!!
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d",&mx[i]);
	}
	for(int i=1;i<=200;++i){
		usd1[i]=0;
		usd[i]=0;
		for(int j=1;j<=200;++j){
			for(int k=0;k<=10;++k){
				val[i][j][k]=0;
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
			if(a[i][j]){
				val[i][a[i][j]][++val[i][a[i][j]][0]]=j;
			}
		}
	}
	for(int i=1;i<=n;++i){
		a[i][0]=m+1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&exp[i]);
	}
	calc1();
	for(int i=1;i<=n;++i){
		printf("%d ",a[i][usd1[i]]);
	}
	puts("");
	int l,r,mid,ans;
	for(int i=1;i<=n;++i){
		if(a[i][usd1[i]]<=exp[i]){
			printf("0 ");
			continue;
		}
		l=1,r=i-1,ans=0;
		while(l<=r){
			mid=(l+r)>>1;
			if(chck(i,mid)){
				ans=mid;
				l=mid+1;
			}else{
				r=mid-1;
			} 
		}
		printf("%d ",i-ans);
	}
	puts("");
}

int main(){
	int T;
	scanf("%d%d",&T,&c);
	while(T--){
		init();
	}
	return 0;
}

lp3455 POI2007 ZAP-Queries

曾经有一道题,叫做YY的GCD,它求的是这样一个值:
$$\begin{equation}\begin{split}\sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{p\in P}[gcd(x,y)==p] \end{split}\end{equation}$$
然后观察这道题的求和式:
$$\begin{equation}\begin{split}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==d] \end{split}\end{equation}$$
长得很像对不对?
事实上就是前者的简化版。
剩下的操作就很套路了。
$$\begin{equation}\begin{split}&\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(x,y)==1]\\=&\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{k|gcd(x,y)}\mu(k)\\=&\sum_{x=1}^{\lfloor\frac{n}{dk}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{dk}\rfloor}\mu(k)\\=&\sum_{k=1}^{min(n,m)}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor \end{split}\end{equation}$$
然后预处理出莫比乌斯函数跑数论分块即可。

#include<iostream>
#include<cstdio>

const int N = 100000+5;

int p[N/10],mu[N],n,m,d;
bool ip[N];
void prpr(){
	p[0]=0;mu[1]=1;ip[1]=1;
	for(int i=2;i<=100000;++i){
		if(!ip[i]){
			p[++p[0]]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=p[0]&&p[j]*i<=100000;++j){
			ip[i*p[j]]=1;
			if(!(i%p[j])){
				mu[i*p[j]]=0;
				break;
			}else{
				mu[i*p[j]]=-mu[i];
			}
		}
	}
	for(int i=2;i<=100000;++i){
		mu[i]+=mu[i-1]; 
	}
}
long long ans;
void init(){
	scanf("%d%d%d",&n,&m,&d);
	n>m?n^=m^=n^=m:0;
	ans=0;
	int k=0;
	for(int i=1;i<=n;i=k+1){
		k=std::min(n/(n/i),m/(m/i));
		ans+=1ll*(n/(i*d))*(m/(i*d))*(mu[k]-mu[i-1]);
	}
	printf("%lld\n",ans);
}

int main(){
	prpr();
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

lp4363 九省联考2018 一双木棋chess

快要省选了,需要学习一些乱搞操作。
在这里学习一下Min-Max对抗搜索。
首先了解一下Min-Max对抗搜索。
首先我们知道,对于一个零和有限信息确定性博弈游戏,我们可以将整个游戏的所有局面建成一个有向图。而在几乎所有此类游戏中,整个游戏的所有局面应当能组成一个DAG。
对于这样一个DAG,我们可以对它进行分层,最后得到的应当是一张分层图。这张分层图上的每一层象征着一方正在进行操作。
那么显然这个游戏的最终解是可以知道的。无非就是直接把整张图DFS一遍罢了。
然而,在绝大部分游戏中,这么做的复杂度都太大了,以至于根本无法接受。我们考虑一种被称为Min-Max对抗搜索的搜索方法。
我们首先定义先手方为Max方,后手方为Min方,然后设置一个搜索范围。那么每一个节点的值是这样确定的:
如果它的深度是搜索深度边缘,亦或者它干脆就是一个终止局面,那么它的值就是一个精心设计的估价函数的值。这个估价函数应当能够较好地估计整个局面倾向于哪一方。
如果这个节点是由Max方行动,那么它的值是所有子局面里的值的最大值,因为Max方会向对自己最有利的局面走。
如果这个节点是由Min方行动,那么它的值是所有子局面里的值的最小值,因为Min方会向对Max方最不利的局面,也就是对自己最有利的局面走。
这样就能够求得当前局面的权值,从而得到一个较优秀的决策支了。
本来打算学一下alpha-beta剪枝的,但是这一题好像不是很需要…

回到这一题,如果我们暴力储存每一个状态,那么很显然时间会爆炸。有没有更好的思路呢?
直觉告诉我们,一个格子放置的次序和答案是没有关系的。所以我们不妨假定当前放置的格子总是左上角的一整个块。这样状态数大概就在10^10以内了。
然而实际上并不需要这么多的状态。所以可以Hash以后用map离散化。

#include<iostream>
#include<cstdio>
#include<tr1/unordered_map>

inline int Max(int A,int B){
	return A>B?A:B;
}

inline int Min(int A,int B){
	return A<B?A:B;
}
const int INF=0x3f3f3f3f;
std::tr1::unordered_map<long long,int> mp;
int a[11][11],b[11][11],f[11],n,m;

inline long long hsh(){
	long long RT=0;
	for(int i=1;i<=n;++i){
		RT*=12;
		RT+=f[i];
	}
	return RT;
}

inline void ahsh(long long X){
	for(int i=n;i>=1;--i){
		f[i]=X%12;
		X/=12;
	}
}

inline int dfs(long long X,bool typ){
	if(mp.count(X)){
		return mp[X];
	}
	int RT=typ?-INF:INF;
	long long nw;
	ahsh(X);
	for(int i=1;i<=n;++i){
		if(f[i]<f[i-1]){
			++f[i];nw=hsh();
			RT=typ?Max(RT,dfs(nw,0)+a[i][f[i]]):Min(RT,dfs(nw,1)-b[i][f[i]]);
			--f[i];
		}
	}
	return mp[X]=RT;
}

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&b[i][j]);
		}
	}
	for(int i=0;i<=n;++i){
		f[i]=m;
	}
	mp[hsh()]=0;
	printf("%d\n",dfs(0,1));
}

int main(){
	init();
	return 0;
}

lp4245 【模板】任意模数NTT

我们首先考虑一个很暴力的玩法,直接找一个很大很大很大的模数,然后用int128上一个朴素NTT,再将结果对题目给的模数取模,似乎就可以了。
然而仔细考虑一下发现这个做法实在太暴力了(才不是因为找不到合适的模数呢。)我们考虑另一种方案。
现在假设我们已经用好几种模数求出最终的各种值了,那么原值是多少呢?很显然可以用中国剩余定理来求出。
我们计算了一下,发现只要用三个质数,值域就足以用中国剩余定理求出最终值了。
然而我们知道,模运算没有交换律。故而我们不能用常规的中国剩余定理合并,应该需要使用一种类似于扩展中国剩余定理的递推合并方法来合并它们的解。
这就完成了任意模数的NTT。
另外要注意数组大小…

#include<iostream>
#include<cstdio>

inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}

inline long long mlt(long long A,long long X,long long P){
	long long BS=A,RT=0;
	while(X){
		if(X&1){
			RT+=BS;
			RT%=P;
		}
		BS+=BS;
		BS%=P;
		X>>=1;
	}
	return RT;
}

inline long long pw(long long A,long long X,long long P){
	long long BS=A,RT=1;
	while(X){
		if(X&1){
			RT*=BS;
			RT%=P;
		}
		BS*=BS;
		BS%=P;
		X>>=1;
	}
	return RT;
}

const long long MOD[3]={469762049,998244353,1004535809};
const long long MM=468937312667959297;
const long long g0=3,gi[3]={156587350,332748118,334845270};

int L=1,inv[3],R[1<<21|1];
inline void prpr(int LEN){
	int B=0;
	while(L<=LEN){
		L<<=1;
		++B;
	}
	for(int i=0;i<3;++i){
		inv[i]=MOD[i]-(MOD[i]-1)/L;
	}
	for(int i=0;i<L;++i){
		R[i]=R[i>>1]>>1|(i&1)<<(B-1);
	}
}

inline void NTT(int *A,int typ,int P){
	for(int i=0;i<L;++i){
		if(R[i]<i){
			Swap(A[i],A[R[i]]);
		}
	}
	int bs,nw,X,Y,M;
	for(int i=2;i<=L;i<<=1){
		M=i>>1;
		bs=pw(~typ?g0:gi[P],(MOD[P]-1)/i,MOD[P]);
		for(int j=0;j<L;j+=i){
			nw=1;
			for(int k=0;k<M;++k,nw=1ll*nw*bs%MOD[P]){
				X=A[j+k],Y=1ll*nw*A[j+k+M]%MOD[P];
				A[j+k]=(X+Y)%MOD[P];
				A[j+k+M]=(X-Y+MOD[P])%MOD[P];
			}
		}
	}
}
int C[1<<21|1],D[1<<21|1],ans[3][1<<21|1];
inline void FNTT(int *A,int *B,int P){
	for(int i=0;i<L;++i){
		C[i]=A[i],D[i]=B[i];
	}
	NTT(C,1,P);
	NTT(D,1,P);
	for(int i=0;i<L;++i){
		C[i]=1ll*C[i]*D[i]%MOD[P];
	}
	NTT(C,-1,P);
	for(int i=0;i<L;++i){
		ans[P][i]=(int)(1ll*(C[i]+MOD[P])*inv[P]%MOD[P]);
	}
}
int a[1<<21|1],b[1<<21|1],n,m,p;
long long t[3];
void init(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=0;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=0;i<=m;++i){
		scanf("%d",b+i);
	}
	prpr(n+m);
	FNTT(a,b,0);FNTT(a,b,1);FNTT(a,b,2);
	t[0]=pw(MOD[1]%MOD[0],MOD[0]-2,MOD[0]);t[1]=pw(MOD[0]%MOD[1],MOD[1]-2,MOD[1]);t[2]=pw(MM%MOD[2],MOD[2]-2,MOD[2]);//分别求出要用到的三个逆元。 
	long long T1,T2;
	for(int i=0;i<=n+m;++i){
		T1=(mlt(1ll*ans[0][i]*MOD[1]%MM,t[0],MM)+mlt(1ll*ans[1][i]*MOD[0]%MM,t[1],MM))%MM;//直接用CRT合并一二式。 
		T2=((ans[2][i]-T1)%MOD[2]+MOD[2])%MOD[2]*t[2]%MOD[2];//用EXCRT将第三式合并之。 
		printf("%d ",(int)(((T2%p)*(MM%p)%p+T1%p)%p));//求得最终解。 
	}
}

int main(){
	init();
	return 0;
}