lp3902 递增

最长上升子序列裸题。
dp+二分即可。

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

const int N=100005;
const int INF=0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}
int n,a[N],f[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	memset(f,0x3f,sizeof(f));
	f[1]=a[1];
	int pos,ans=1;
	for(int i=2;i<=n;++i){
		pos=lower_bound(f+1,f+1+n,a[i])-f-1;
		ans=Max(ans,pos+1);
		f[pos+1]=Min(f[pos+1],a[i]);
	}
	printf("%d\n",n-ans);
}

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

lp1438 无聊的数列

区间加上一个等差数列这件事情其实并不好维护。但既然是单点查询,那就可以考虑差分。
我们考虑将数列差分,维护一个差分数列。于是区间 [l,r] 加上等差数列 {K,D},就变成了三个操作:
点 l 加上 K
区间 [l+1,r] 加上 D
点 r+1 减去 K+(r-l)*D
对于每个查询求前缀和即可。

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

const int N=100005;
int n,m;
ll a[N];
ll val[N<<2],tag[N<<2];
inline void pshd(int L,int R,int X){
	int MID=(L+R)>>1;
	tag[X<<1]+=tag[X];tag[X<<1|1]+=tag[X];
	val[X<<1]+=tag[X]*(MID-L+1);val[X<<1|1]+=tag[X]*(R-MID);
	tag[X]=0;
}
inline void updt(int X){
	val[X]=val[X<<1]+val[X<<1|1];
}
ll qry(int L,int R,int A,int B,int X){
	if(A<=L&&B>=R){
		return val[X];
	}
	int MID=(L+R)>>1;ll ret=0;
	pshd(L,R,X);
	if(A<=MID){
		ret+=qry(L,MID,A,B,X<<1);
	}
	if(B>MID){
		ret+=qry(MID+1,R,A,B,X<<1|1);
	}
	return ret;
}
void mdf(int L,int R,int A,int B,int X,ll V){
	if(A<=L&&B>=R){
		tag[X]+=V;
		val[X]+=V*(R-L+1);
		return;
	}
	int MID=(L+R)>>1;
	pshd(L,R,X);
	if(A<=MID){
		mdf(L,MID,A,B,X<<1,V);
	}
	if(B>MID){
		mdf(MID+1,R,A,B,X<<1|1,V);
	}
	updt(X);
}
void build(int L,int R,int X){
	if(L==R){
		val[X]=a[L];
		return;
	}
	int MID=(L+R)>>1;
	build(L,MID,X<<1);
	build(MID+1,R,X<<1|1);
	updt(X);
}
inline void chg(int L,int R,ll V){
	if(L>R||L<1||R>n){
		return;
	}
	mdf(1,n,L,R,1,V);
}
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=n;i>1;--i){
		a[i]-=a[i-1];
	}
	build(1,n,1);
	ll opt,l,r,k,d,p;
	for(int i=1;i<=m;++i){
		scanf("%lld",&opt);
		if(opt==1){
			scanf("%lld%lld%lld%lld",&l,&r,&k,&d);
			chg(l,l,k);chg(l+1,r,d);chg(r+1,r+1,-(k+d*(r-l)));
		}else{
			scanf("%lld",&p);
			printf("%lld\n",qry(1,n,1,p,1));
		}
	}
}

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

lp2757 [国家集训队]等差子序列

因为只要求存在性,故而观察到长度>3的等差序列只需要求前3项即可。
于是就转化为求 $$ a_j+a_k=2*a_i $$ 是否存在。
观察到数据范围 n<=10000 ,于是用两个 bitset 分别维护前缀桶和后缀桶,稍微左右移一下求交即可。

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

*/
const int N=10005;
bitset<N> pre,lst;
int n,a[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	pre.reset();lst.reset();
	for(int i=2;i<=n;++i){
		lst[n-a[i]]=1;
	}
	for(int i=2;i<n;++i){
		pre[a[i-1]]=1;lst[n-a[i]]=0;
		if(((2*a[i]>=n?lst<<(2*a[i]-n):lst>>(n-2*a[i]))&pre).any()){
			puts("Y");
			return;
		}
	}
	puts("N");
}

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

lp1341 无序字母对

仔细观察这题:考虑到字母对可以反向,我们不妨把它们看作无序数对。这就把题意转化为了,给你n个无序数对,让你找到一个n+1个数的序列,使得无序数对在序列的相邻两项中各自至少出现一次。
观察到这无序数对组和图的相似性,我们可以尝试把无序数对看成一条边,然后建一张图。在这种情况下,这个序列就是这张图上的一个遍历顺序,使得经过每一条边至少一次。
深入考虑,这个序列也只能经过每条边至多一次。这是因为,一条n条边的路径,恰好包含了n+1个点。
问题就转化为了欧拉路径问题。

判断一张图是否是半欧拉图是很容易的。一张半欧拉图中,恰好有两个点的度数为奇数——这两个点各自作为欧拉路径的起点和终点。
求解欧拉回路的方法是很容易的。对于每一个点,我们只需要找到与它相邻的所有环即可。
问题在于——这很不显然——为什么相同的求法放到欧拉路径上,只需从奇数入度点开始,就是合法的?
我们不妨把整个欧拉路径抽象成一条链上面挂着一堆环套环套环套环套环。一个令人好奇的问题是,为什么搜索的时候不会直接走到链的另一端,而是先把环跑完,或者反过来?
我们注意到把点加入答案数组的方式:对于两个栈——答案栈和搜索栈来说,点被加入的顺序是不仅相同的。
模拟一下,一个点能从搜索栈出来,被加入答案栈,当且仅当从这个点出发无路可走了。
显然,有且仅有终点是无路可走的。那么,无论终点是在什么时候被访问到的,只要它被访问到,那么它就会被立刻退出搜索栈并被加入答案栈,剩下的点也是同理。

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

int hash[200];int hsah[200];
int mp[60][60],in[60];
int n;
int st[3005],tp=0;
inline void dfs(int X){
	for(int i=0;i<52;++i){
		if(mp[X][i]){
			printf("%d %d\n",X,i);
			--mp[X][i],--mp[i][X];
			dfs(i);
		}
	}
	printf("%d\n",X); 
	st[++tp]=X;
}
void init(){
	for(int i=0;i<26;++i){
		hash['A'+i]=i;hash['a'+i]=i+26;
		hsah[i]='A'+i;hsah[i+26]='a'+i;
	}
	scanf("%d",&n);
	char ch[4];
	for(int i=1;i<=n;++i){
		std::cin>>ch+1;
		++mp[hash[ch[1]]][hash[ch[2]]],++mp[hash[ch[2]]][hash[ch[1]]];
		++in[hash[ch[1]]],++in[hash[ch[2]]];
	}
	int ans=0,nans=-1;
	for(int i=0;i<52;++i){
		if(in[i]&1){
			++ans;
			if(nans<0){nans=i;}
		}
	}
	if(ans&&ans!=2){
		puts("No Solution");
		return;
	}
	if(!ans){
		for(int i=0;i<52;++i){
			if(in[i]){
				nans=i;
				break;
			}
		}
	}
	dfs(nans);
	if(tp!=n+1){
		puts("No Solution");
		return;
	}
	while(tp){
		putchar(hsah[st[tp--]]);
	}
}
int main(){
	init();
	return 0;
}

lp5395 【模板】第二类斯特林数·行

第二类斯特林数,指的是一组表示「将n个不同的元素划分为m个非空不相交集的方案数」的组合数。有时写作\(S(n,m)\)或\(\left\{\begin{matrix}n\\m\end{matrix}\right\}\)
从题意来看,我们可以容易地想到一个递推方案:每个新的元素,可以为它新开一个集合,或者放到已有的任何一个集合里面。所以我们得到一个递推式:
$$S(n,m)=S(n-1,m-1)+m*S(n-1,m)$$
然后问题是怎么求值。

首先我们有一个式子,我们称之为二项式反演的通项式。
$$ f(n)=\sum_{i=0}^nC_{n}^{i}g(n) \Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}C_{i}{n}f(n)$$
举个例子:
$$\begin{matrix} f_{1}&=&g_{1}\\f_{2}&=&g_{1}&+&g_{2}\\f_{3}&=&g_{1}&+&2*g_{2}&+&g_{3}\\f_{4}&=&g_{1}&+&3*g_{2}&+&3*g_{3}&+&g_{4} \end{matrix}$$

由此可得:

$$\begin{matrix} g_{1}&=&f_{1}\\g_{2}&=&f_{2}&-&f_{1}\\g_{3}&=&f_{3}&-&2*g_{2}&-&g_{1}\\&=&f_{3}&-&2*f_{2}&+&f_{1}\\g_{4}&=&f_{4}&-&3*g_{3}&-&3*g_{2}&-&g_{1}\\&=&f_{4}&-&3*f_{3}&-&3*g_{2}&-&4*g_{1}\\&=&f_{4}&-&3*f_{3}&+&3*f_{2}&-&f_{1} \end{matrix}$$

然后我们考虑\(m^n\)的组合意义,也就是,将\(n\)个不同的球,放到\(m\)个不同的盒子(可以有空盒)的方案数。
我们不妨枚举有装东西的盒子的个数。令它为\(i\),那么选取这些盒子的方案数即是\(C_{m}^{i}\)。
选取了盒子之后,问题就转化为了将\(n\)个不同物品装到\(m\)个不同盒子里,使得每个盒子非空。这就相当于,将\(n\)个不同物品装到\(m\)个相同盒子里,使得每个盒子非空的方式——也就是\(S(n,m)\),乘上盒子的排列顺序——也就是\(m!\)。
形式化的说,就是:
$$m^n=\sum_{i=0}^{m}S(n,i)i!C_{m}^{i}$$
我们发现这个式子的形式符合二项式反演的通项式。
因而我们将\(m^n\)作为\(f\),将\(S(n,i)i!\)作为\(g\)。
那么反演得到:
$$S(n,m)=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}i^nC_{m}^{i}$$
考虑\(C_{m}^{i}=\frac{m!}{i!(m-i)!}\),我们可以将上式化简得到:
$$S(n,m)=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
于是我们有:
$$\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
考虑函数卷积的本质,对于卷积\(f=gu\),其本质是: $$f(n)=\sum_{i=0}^{n}g(i)u(n-i)$$ 因而,我们发现,上式本质上就是: $$\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{i=0}^{m}\frac{(-1)^{m-i}}{(m-i)!}*\frac{i^n}{i!}$$
上一个NTT卷积一下就好了。

#include<iostream>
#include<cstdio>

#define Swap(A,B) (A^=B^=A^=B)
const long long P=167772161;
const long long g0=3,gi=55924054;
int L=1,R[1<<21|1];
long long invL;
inline int pw(int A,int X){
	long long BS=A,RT=1;
	while(X){
		if(X&1){
			RT=RT*BS%P;
		}
		BS=BS*BS%P;
		X>>=1;
	}
	return RT;
}
inline void prpr(int LEN){
	int B=0;
	while(L<=LEN){
		L<<=1;
		++B;
	}
	invL=P-(P-1)/L;
	for(int i=0;i<L;++i){
		R[i]=R[i>>1]>>1|(i&1)<<(B-1);
	}
}
inline void FNTT(int *A,int typ){
	for(int i=0;i<L;++i){
		if(R[i]<i){
			Swap(A[R[i]],A[i]);
		}
	}
	int gn,g,X,Y,M;
	for(int i=2;i<=L;i<<=1){
		M=i>>1;
		gn=pw(~typ?g0:gi,(P-1)/i);
		for(int j=0;j<L;j+=i){
			g=1;
			for(int k=0;k<M;++k,g=1ll*g*gn%P){
				X=A[j+k],Y=1ll*g*A[M+j+k]%P;
				A[j+k]=(X+Y)%P,A[M+j+k]=(X-Y)%P;
			}
		}
	}
}
int n,a[1<<21|1],b[1<<21|1],inv[1<<21|1];
void init(){
	scanf("%d",&n);
	prpr(n+1<<1);
	inv[0]=inv[1]=1;
	for(int i=2;i<=n;++i){
		inv[i]=1ll*(P-P/i)*inv[P%i]%P;
	}
	for(int i=1;i<=n;++i){
		inv[i]=1ll*inv[i-1]*inv[i]%P;
	}
	for(int i=0;i<=n;++i){
		a[i]=1ll*pw(-1,i)*inv[i]%P;
		b[i]=1ll*pw(i,n)*inv[i]%P;
	}
	FNTT(a,1);
	FNTT(b,1);
	for(int i=0;i<L;++i){
		a[i]=1ll*a[i]*b[i]%P;
	}
	FNTT(a,-1);
	for(int i=0;i<=n;++i){
		printf("%d ",1ll*(a[i]+P)*invL%P);
	}
}

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

lp2501 HAOI2006 数字序列

我们分别考虑一二问。
对于第一问,我们思考一个子序列是合法的「不用修改」的子序列的充要条件。
容易想到的,这个条件是:
$$ \forall i,j\in S, i=j-i$$
自然语言化地说,就是,对于这个不用修改的子序列中的任意两个元素,它们的值的差距至少要大于它们间的元素个数,这样才能放得下它们中间的元素。
移项,我们得到:
$$a_j-j>=a_i-i$$
所以,我们令\(b_i=a_i-i\),那么第一问中不用修改的个数就是\(b\)的最长不下降子序列长度。
对于第二问,首先,它可以被转化为「最小修改代价求\(b\)单调不减」。
我们有一个结论:相邻两关键点\(i,j\)间一定可以找到一条分界线,使得线左端的所有点变化成\(b_i\),右端所有点变化成\(b_j\)会最优。
这是如何证明的呢?
首先,我们知道,\(i,j\)之间的任意一个点,它的值必然要小于\(b_i\)或者大于\(b_j\),否则选取这个点只会让答案更优。
然后,我们尝试进行反证。如果有一个点修改以后位于中间,并且它可以被修改到某一边,那么显然修改到某一边之后答案会更小。
如果将分界线定在某处,会使得某些点与它们的最优处于的边不相同,那么考虑这些点与分界点之间的其他点的数量。
如果其他点的数量小于这些点,那么不妨把这些点修改后的位置换到另一边,这样答案就变小了点数差*上下两边距离。
否则,不如不修改。
所以我们证明了这个结论。
然后是关于时间复杂度的。可以证明,在序列随机的情况下,最长不下降子序列的期望长度是logn级别的。(我不会证,也找不到文章。求大佬教教我)

注意:要提前把\(b_0\)设成\(-INF\),并在末尾插入一个\(INF\)的点。

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

typedef long long ll;
const int N=35005;
const int INF=0x3f3f3f3f;
inline ll Abs(ll X){
	return X>=0?X:-X;
}
inline ll Min(ll A,ll B){
	return A<B?A:B;
}
int n,a[N],b[N],nm[N];
ll f[N],sm1[N],sm2[N];
struct ee{
	int v;
	int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		b[i]=a[i]-i;
	}
	int cnt=0,nw;
	b[0]=-INF;f[0]=-INF;
	b[++n]=INF;
	for(int i=1;i<=n;++i){
		if(b[i]>=f[cnt]){
			f[++cnt]=b[i];
			nm[i]=cnt;
		}else{
			nw=upper_bound(f+1,f+cnt,b[i])-f;
			f[nw]=b[i];
			nm[i]=nw;
		}
	}
	printf("%d\n",n-cnt);
	for(int i=n;i>=0;--i){
		add(nm[i],i);
		f[i]=INF;
	}
	f[0]=0;
	int v;
	for(int i=1;i<=n;++i){
		for(int j=h[nm[i]-1];j;j=e[j].nxt){
			v=e[j].v;
			if(v>i||b[v]>b[i]){
				continue;
			}
			sm1[v]=0;
			for(int k=v+1;k<=i;++k){
				sm1[k]=sm1[k-1]+Abs(b[k]-b[v]);
			}
			sm2[i-1]=0;
			for(int k=i-2;k>=v;--k){
				sm2[k]=sm2[k+1]+Abs(b[k+1]-b[i]);
			}
			for(int k=v;k<i;++k){
				f[i]=Min(f[i],f[v]+sm1[k]+sm2[k]);
			}
		}
	}
	printf("%lld\n",f[n]);
}
int main(){
	init();
	return 0;
}

lp3233 HNOI2014 世界树

让我们来分析这道题。
我们很容易地可以发现,如果一个节点是末端节点,那么它肯定是由它祖先中的第一个节点管辖更优。
由此我们继续推导,可以发现,假如只有两个关键点的话,它们之间的链上一定可以找到一个分界线,使得这条分界线的一段——以及所有与链上这一端相邻的节点——放在一个关键点上,并把剩下的放在另一个关键点上。这样是最优的。
然后我们考虑有三个关键点的情况。如果有三个关键点的话,问题似乎就复杂了很多,这是因为这条分界线必须是基于三个节点共同决定的。
我们换一个思路考虑。求出三个关键点两两的LCA。那么,这一分界线就必然可以在这六个点(最多六个)两两之间的链上找到。
存在一种叫做「虚树」的数据结构。这个数据结构本质上就是将所有关键点以及关键点两两之间的LCA建成一个数。
我们如此考虑,如果有一个点是关键点,那么它向下能够管辖的点的数量就是它的子树大小减去它的所有子节点能管辖的点数之和。
它向上能够管辖的点的数量则相对比较复杂。
我们考虑每一条边,假设我们已经预处理出了虚树上每一个点相邻最近的关键点,那么,如果这条边两端的点相邻最近的关键点是相同的,那么这条边(以及和这条边相邻的所有点)都划归到那个关键点下管辖。
如果这条边两段的点相邻最近的关键点不同,则需要使用倍增来确定这条边要如何被划分成两个部分。

接下来要考虑如何确定虚树上每一个点相邻最近的关键点。
我们不妨这样考虑:一个点相邻最近的关键点如果在它的下方,那么这可以通过树形DP求得;如果在它的上方或者其他子树内呢?
显然,如果这个点的相邻最近关键点在它的上方或者和它不在同一子树内,那么它的父亲的最近关键点一定与这个点的最近关键点相同。
于是,我们不妨从上而下DP,求得这个点在上方或者不在同一子树的最近关键点。

现在我们来梳理一下这一题的思路。
首先,我们进行预处理,处理出每个点的深度和dfn。
然后,我们进行两次树形DP,求出每个点的最近关键点。
第三,我们预处理出所有「末端节点」——也就是所有「是一个虚树上节点的直接儿子且子树内没有关键点的原树上的点」。这些点的贡献可以直接统计到它们父亲的最近关键点。
最后,我们依次考虑剩下的虚树边上的点。如果两段的最近关键点相同,那么就统计到那个最近关键点。否则就进行倍增寻找答案。

顺便讲一下如何建虚树。
我们将所有关键点按照dfs序排序,然后建一个栈,代表当前正在向下延长的链。
如果当前的点与栈顶的LCA的深度小等于次栈顶,那么就说明当前点不在栈顶的子树里,也就意味着栈顶处于当前应该维护的链外。
于是,我们需要就可以将新的这个点加入虚树和栈中。
否则,就说明原来的栈顶需要被弹出,那么就处理完它应该连的边然后将它弹出。

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

typedef pair<int,int> pii;
const int N=300005;
const int INF=0x3f3f3f3f;
struct ee{
	int v;
	int nxt;
}e[1200005];
int h[N],g[N],et=0;
inline void add(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}

int dfn[N],cnt=0,sz[N],dep[N],fa[N][20];
inline void dfs0(int X){
	dfn[X]=++cnt;sz[X]=1;
	Fv(i,X){
		if(e[i].v==fa[X][0]){
			continue;
		}
		fa[e[i].v][0]=X;dep[e[i].v]=dep[X]+1;
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
int usd[N],pt[N],ppt[N],hr[N],ans[N],up[N];
pii nr[N];
inline void dfs1(int X){
	nr[X]=(usd[X]?pii(0,X):pii(INF,0));
	Fv2(i,X){
		dfs1(e[i].v);
		nr[X]=min(nr[X],pii(nr[e[i].v].first+dep[e[i].v]-dep[X],nr[e[i].v].second));
	}
}
inline void dfs2(int X,int D,int P){
	if(pii(D,P)<nr[X]){
		nr[X]=pii(D,P);
	}else{
		D=nr[X].first,P=nr[X].second;	
	}
	Fv2(i,X){
		dfs2(e[i].v,D+dep[e[i].v]-dep[X],P);
	}
}
//子节点中所有子树中有虚树上节点的点都是不可以选取的。
//我们不妨逆向考虑,枚举每一个虚树上的子节点,然后从那个节点开始倍增,一直倍增到这棵树的子节点,然后把这些子节点的子树挖掉。 
inline void dfs3(int X){
	ans[hr[X]=nr[X].second]+=sz[X];
	Fv2(i,X){
		int nw=e[i].v;
		for(int j=18;j>=0;--j){
			if(fa[nw][j]&&dep[fa[nw][j]]>dep[X]){
				nw=fa[nw][j];
			}
		}
		ans[hr[X]]-=sz[up[e[i].v]=nw];
		dfs3(e[i].v);
	}
}
//现在剩下的末端节点就只有虚树上的节点了。 
//如果子节点的dfs序大于当前节点,那么分割点就偏上;否则偏下。 
inline void dfs4(int X){
	Fv2(i,X){
		if(hr[e[i].v]==hr[X]){
			ans[hr[X]]+=sz[up[e[i].v]]-sz[e[i].v];
		}else{
			int len=dep[hr[e[i].v]]+dep[X]-nr[X].first;
			len=((len&1)?(len+1)>>1:((len>>1)+(int)(hr[e[i].v]>hr[X])));
//			这里比较的是编号!!! 
			int nw=e[i].v;
			for(int j=18;j>=0;--j){
				if(dep[fa[nw][j]]>=len){
					nw=fa[nw][j];
				}
			}
			ans[hr[e[i].v]]+=sz[nw]-sz[e[i].v];
			ans[hr[X]]+=sz[up[e[i].v]]-sz[nw];
		}
		dfs4(e[i].v);
	}
}
inline void dfs5(int X){
	up[X]=hr[X]=0;
	Fv2(i,X){
		dfs5(e[i].v);
	}
	g[X]=0;
}
inline bool cmp(int A,int B){
	return dfn[A]<dfn[B];
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		swap(X,Y);
	}
	for(int i=18;i>=0;--i){
		if(dep[fa[X][i]]>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
int st[N],tp=0;
void init(){
	int n,Q;
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(h,u,v);
		add(h,v,u);
	}
	dep[1]=1;
	dfs0(1);
	for(int j=1;j<=18;++j){
		for(int i=1;i<=n;++i){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	scanf("%d",&Q);
	int m,X,Y;
	while(Q--){
		scanf("%d",&m);
		for(int i=1;i<=m;++i){
			scanf("%d",&pt[i]);
			ppt[i]=pt[i],usd[pt[i]]=1;
		}
		sort(pt+1,pt+1+m,cmp);
		st[tp=1]=pt[1];
		for(int i=2;i<=m;++i){
			X=pt[i],Y=lca(X,st[tp]);
			while(tp>1&&dep[Y]<=dep[st[tp-1]]){
				add(g,st[tp-1],st[tp]);
				--tp;
			}
			if(Y!=st[tp]){
				add(g,Y,st[tp]);st[tp]=Y;
			}
			st[++tp]=X;
		}
		while(tp>1){
			add(g,st[tp-1],st[tp]);
			--tp;
		}
		dfs1(st[1]);
		dfs2(st[1],nr[st[1]].first,nr[st[1]].second);
		dfs3(st[1]);
		dfs4(st[1]);
		ans[hr[st[1]]]+=sz[1]-sz[st[1]];
		for(int i=1;i<=m;++i){
			printf("%d ",ans[ppt[i]]);
		}
		puts("");
		dfs5(st[1]);
		for(int i=1;i<=m;++i){
			ans[pt[i]]=0,usd[pt[i]]=0;
		}
	}
}
int main(){
	init();
	return 0;
}

lp4717 【模板】快速沃尔什变换

快速沃尔什变换是一种类似于快速傅里叶变换的操作。它是用来处理子集卷积的有效工具。
我们依次考虑操作符为and or或者xor时的情况。
我们如是考虑:将一个长度为\(2^n\)的数列\(A_{0}\)和\(A_{1}\)切割成两个长度为\(2^{n-1}\)的部分,\(A_{0}\)表示下标最高位为0的数列,而\(A_{1}\)表示下标最高位1的数列。
那么,我们有很显然的and的式子:
$$ C_{0}=A_{0} * B_{0}$$ $$ C_{1}=A_{0} * B_{1} + A_{1} * B_{0} + A_{1} * B_{1}=(A_{0} + A_{1})*(B_{0} + B_{1}) – C_{0}$$
同理,我们可以得到or的式子。
$$C_{0}=A_{0} * B_{0} + A_{1} * B_{0} + A_{0} * B_{1} = (A_{0} + A_{1}) * (B_{0} + B_{1}) -C_{1}$$ $$C_{1}=A_{1} * B_{1}$$
以及xor的式子:
$$C_{0} = A_{0} * B_{0} + A_{1} * B_{1}$$ $$C_{1} = A_{0} * B_{1} + A_{1} * B_{0}$$
我们发现,除了xor以外的式子,都是「简洁」的。
换而言之,我们可以直接以\(nlog_n\)的复杂度求得它们的答案。
现在考虑xor这个玄妙的式子。
我们发现有如下性质:
$$C_{0} + C_{1} = (A_{0} + A_{1}) * (B_{0} + B_{1})$$ $$C_{0} – C_{1} = (A_{0} – A_{1}) * (B_{0} – B_{1})$$
我们不妨令:
$$X = (A_{0} + A_{1}) * (B_{0} + B_{1})$$ $$Y = (A_{0} – A_{1}) * (B_{0} – B_{1})$$
那么
$$ C_{0} = \frac{X + Y}{2}$$ $$ C_{1} = \frac{X – Y}{2}$$
于是就做完了。

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

typedef long long ll;
const ll MOD=998244353;
const ll inv2=(MOD+1)>>1;
inline void fwtor(int *A,int *B,int *C,int N){
	if(N==1){
		C[0]=1ll*A[0]*B[0]%MOD;return;
	}
	int M=N>>1;
	for(int i=0;i<M;++i){
		A[i+M]+=A[i];A[i+M]%=MOD;
		B[i+M]+=B[i];B[i+M]%=MOD;
	}
	fwtor(A,B,C,M);fwtor(A+M,B+M,C+M,M);
	for(int i=0;i<M;++i){
		C[i+M]-=C[i]-MOD;C[i+M]%=MOD;
	}
}
inline void fwtand(int *A,int *B,int *C,int N){
	if(N==1){
		C[0]=1ll*A[0]*B[0]%MOD;return;
	}
	int M=N>>1;
	for(int i=0;i<M;++i){
		A[i]+=A[i+M];A[i]%=MOD;
		B[i]+=B[i+M];B[i]%=MOD;
	}
	fwtand(A,B,C,M);fwtand(A+M,B+M,C+M,M);
	for(int i=0;i<M;++i){
		C[i]-=C[i+M]-MOD;C[i]%=MOD;
	}
}
inline void fwtxor(int *A,int *B,int *C,int N){
	if(N==1){
		C[0]=1ll*A[0]*B[0]%MOD;return;
	}
	int M=N>>1,XA,YA,XB,YB;
	for(int i=0;i<M;++i){
		XA=(A[i]+A[i+M])%MOD,YA=(A[i]-A[i+M]+MOD)%MOD;
		XB=(B[i]+B[i+M])%MOD,YB=(B[i]-B[i+M]+MOD)%MOD;
		A[i]=XA,A[i+M]=YA,B[i]=XB,B[i+M]=YB;
	}
	fwtxor(A,B,C,M),fwtxor(A+M,B+M,C+M,M);
	for(int i=0;i<M;++i){
		XA=(C[i]+C[i+M])%MOD,YA=(C[i]-C[i+M]+MOD)%MOD;
		C[i]=XA*inv2%MOD,C[i+M]=YA*inv2%MOD;
	}
}
int n;
int a[1<<17],b[1<<17],c[1<<17],aa[1<<17],bb[1<<17];
void init(){
	scanf("%d",&n);
	n=1<<n;
	for(int i=0;i<n;++i)scanf("%d",a+i);
	for(int i=0;i<n;++i)scanf("%d",b+i);
	for(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;
	fwtor(aa,bb,c,n);
	for(int i=0;i<n;++i)printf("%d ",c[i]);puts("");
	for(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;
	fwtand(aa,bb,c,n);
	for(int i=0;i<n;++i)printf("%d ",c[i]);puts("");
	for(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;
	fwtxor(aa,bb,c,n);
	for(int i=0;i<n;++i)printf("%d ",c[i]);puts("");
}
int main(){
	init();
	return 0;
}

lp2622 关灯问题II

显然,对于某个状态,按下某个按钮之后,一定会得到另一个状态。
而灯的状态最大只有\(2^10\)。
故而考虑建一张图,2^n个点,m条边,那么答案就是从0到2^n-1的最短距离。
直接BFS即可。

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

const int INF=0x3f3f3f3f;
int n,m;
queue<int> q;
int dep[1025],vis[1025];
int a[15],b[105],c[105];
inline int bfs(){
	for(int i=0;i<(1<<n);++i){
		dep[i]=INF;
	}
	q.push(0);
	dep[0]=0;
	int p,v;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=1;i<=m;++i){
			v=(p|b[i])&c[i];
			if(dep[v]>dep[p]+1){
				dep[v]=dep[p]+1;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return (dep[(1<<n)-1]^INF)?dep[(1<<n)-1]:-1;
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		b[i]=c[i]=0;
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<n;++j){
			scanf("%d",&a[j]);
			if(a[j]==1){
				b[i]|=(1<<j);
				c[i]|=(1<<j);
			}
			if(a[j]==0){
				c[i]|=(1<<j);
			}
		}
	}
	printf("%d\n",bfs());
}
int main(){
	init();
	return 0;
}

lp3950 部落冲突

LCT裸题。

#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=300005;
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,m;
int qu[N],qv[N],tp=0;
void init(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		link(u,v);
	}
	char op[4];
	for(int i=1;i<=m;++i){
		cin>>op+1;
		switch(op[1]){
			case 'Q':{
				scanf("%d%d",&u,&v);
				puts(qryrt(u)==qryrt(v)?"Yes":"No");
				break;
			}
			case 'C':{
				scanf("%d%d",&u,&v);
				++tp;
				cut(qu[tp]=u,qv[tp]=v);
				break;
			}
			case 'U':{
				scanf("%d",&u);
				link(qu[u],qv[u]);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp4582 FJOI2014 树的重心

两个重心的情况想想都麻。我们首先考虑一个重心的情况。 我们把 假设我们现在已经求出了每个子树的大小,那么我们发现,一棵子树有且仅有它的大小是对答案有影响的。所以我们可以预处理出每棵子树的不同大小的联通结构数,然后枚举子树大小瞎统计一下。 那么想想要怎么预处理。我们令\(f_{i,j}\)表示以\(i\)为根节点的子树中选取\(j\)个节点的联通子树的个数,\(g_{i,j}\)表示当前子树前\(i\)个儿子选取\(j\)个的联通子树的个数。 那么,根据定义我们有: $$g_{nw,j}=\sum_{k=1}^{j}g_{nw-1,k}f_{v,j-k}$$ $$f_{X,i}=g_{sum\_of\_sons,i-1}$$ 然后树形DP即可。 仔细想想,如果有两个重心,那么把两个重心的连边断开,两边的答案的统计是互不干扰的。 故而我们可以将原树分成两棵树统计答案,再把答案相乘。

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

const int MOD=10007;
const int INF=0x3f3f3f3f;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[404];
int h[205],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 sz[205],mx[205],rt=0,rt2=0,totsz,Tid=0,n;
inline void dfs0(int X,int FA){
	sz[X]=1;mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA){
			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],totsz-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
		rt2=0;
	}else if(mx[X]==mx[rt]){
		rt2=X;
	}
}
int f[205][205],g[205][205];
inline void dfs1(int X,int FA){
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs1(e[i].v,X);
	}
	for(int i=0;i<=n;++i){
		for(int j=0;j<=n;++j){
			g[i][j]=0;
		}
	}
	f[X][1]=f[X][0]=g[0][0]=sz[X]=1;
	int nw=1;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		sz[X]+=sz[e[i].v];
		for(int j=0;j<=sz[X];++j){
			for(int k=0;k<=j;++k){
				g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[i].v][k]%MOD)%MOD;
			}
		}
		++nw;
	}
	--nw;
	for(int i=1;i<=sz[X];++i){
		f[X][i]=g[nw][i-1];
	}
}
int ans=0;
inline void calc1(){
	ans=1;
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,0);
	for(int i=2;i<=n;++i){
		for(int j=0;j<=n;++j){
			for(int k=0;k<=n;++k){
				g[j][k]=0;
			}
		}
		g[0][0]=1;int nw=1;sz[rt]=1;
		Fv(E,rt){
			sz[rt]+=sz[e[E].v];
			for(int j=0;j<=Min(i-1,sz[rt]);++j){
				for(int k=0;k<=j;++k){
					if(2*k>=i){
						break;
					}
					g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[E].v][k]%MOD)%MOD;
				}
			}
			++nw;
		}
		--nw;
		ans=(ans+g[nw][i-1])%MOD;
	}
}
inline void calc2(){
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,rt2);dfs1(rt2,rt);
	ans=0;
	for(int i=1;i<=n/2;++i){
		ans=(ans+f[rt][i]*f[rt2][i]%MOD)%MOD;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	et=rt=rt2=0;
	for(int i=1;i<=n;++i){
		h[i]=sz[i]=0;
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	totsz=n;
	mx[0]=INF;
	dfs0(1,0);
	if(!rt2){
		calc1();
	}else{
		calc2();
	}
	printf("Case %d: %d\n",Tid,ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		++Tid;
		init();
	}
	return 0;
}

lp1337 JSOI2004 平衡点 or 吊打XXX

首先我们认识一种算法——爬山算法。这种算法总是贪心地接受更优秀的解。
但是,我们知道,并不是所有的解都是一个单峰函数。因此我们有了非常具有魔力的模拟退火算法。
我们想到一种随机化的优化方案,就是对于一个新的解,如果是更优的,就一定接受它;否则,有概率去接受它。
然而这样并不是特别优的,因为如果概率固定,那么它很大意义上还是在瞎JB跳。我们有一种被称为「模拟退火」的算法。我们定义一个全局变量T,令瞎JB跳的概率是\(e^{\frac{\Delta ans}{T}}\),然后我们令\(T\)不断降低,使得最后的答案趋于稳定。
我们相信,只要T足够大、尝试的次数足够多,那么总是能找到最优解。
然而,我们必须明白的是,模拟退火本质上是一种以时间换正确性的算法,因此要如何在时间和正确性之间取得平衡,就成为一个很困难的问题了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<ctime>
#define RD() (T*(rand()*2-RAND_MAX))
using namespace std;

typedef double db;
typedef long double ldb;
const int N=1005;
const ldb dlT=0.97;
const ldb eps=1E-14;
db x[N],y[N],w[N];
int n;
inline ldb calc(db X,db Y){
	db dx,dy,rt=0;
	for(int i=1;i<=n;++i){
		dx=x[i]-X,dy=y[i]-Y;
		rt+=sqrt(dx*dx+dy*dy)*w[i];
	}
	return rt;
}
void init(){
	scanf("%d",&n);
	db smx=0,smy=0;
	int tms=100;
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%lf",x+i,y+i,w+i);
		smx+=x[i],smy+=y[i];
	}
	smx/=n,smy/=n;
	db ans,bst,x0,y0,x1,y1,nw;
	ans=bst=calc(smx,smy);
	srand(time(0));
	while(tms--){
		ans=bst,x0=smx,y0=smy;
		for(db T=100000;T>eps;T*=dlT){
			x1=x0+RD(),y1=y0+RD();
			nw=calc(x1,y1);
//			printf("%lf %lf\n",x1,y1);
			if(nw<bst){
				bst=nw;
				smx=x1,smy=y1;
			}
			if(nw<ans||(exp((ans-nw)/T)>(long double)rand()/RAND_MAX)){
				ans=nw;
				x0=x1,y0=y1;
			}
		}
	}
	printf("%.3lf %.3lf\n",smx,smy);
}
int main(){
	init();
	return 0;
}

lp2387 NOI2014 魔法森林

这一题据说是LCT维护边权的题目。但是我们观察一下感觉可以用动态加边SPFA来跑这道题。 具体来说,对于每一条加进来的边,我们知道,并不是整张图都因为这条边而改变。这条边会改变的有且仅有图的一部分。 因此,我们不妨将所有边按照a的大小排序,然后将b节点作为关键字,跑动态加边SPFA。 然后答案对dis[n]+e[i].a去min即可。这是因为如果它没有影响原来的最短路,那么选择这条边的a肯定不会更优;如果更新了,那么就必须要选择这条边的a。 复杂度大概是松松松,构造了菊花套菊花也没有卡掉,就假装能过吧…求大佬证明。

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

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 N=50005;
const int INF=0x3f3f3f3f;
struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
struct data{
	int u;int v;int a;int b;
	inline bool operator<(const data &B){
		return a^B.a?a<B.a:b<B.b;
	}
}ed[100005];
int h[N],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 dis[N];
bool vis[N];
queue<int> q;
inline void SPFA(int s1,int s2){
	vis[s1]=vis[s2]=1;
	q.push(s1),q.push(s2);
	int p;
	while(!q.empty()){
		p=q.front();q.pop();
		for(int i=h[p];i;i=e[i].nxt){
			if(Max(dis[p],e[i].w)<dis[e[i].v]){
				dis[e[i].v]=Max(dis[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
		vis[p]=0;
	}
}
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;++i){
		dis[i]=INF;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&ed[i].u,&ed[i].v,&ed[i].a,&ed[i].b);
	}
	sort(ed+1,ed+1+m);
	int ans=INF;
	for(int i=1;i<=m;++i){
		add(ed[i].u,ed[i].v,ed[i].b);
		SPFA(ed[i].u,ed[i].v);
		ans=Min(ans,dis[n]+ed[i].a);
	}
	printf("%d\n",ans<INF?ans:-1);
}
int main(){
	init();
	return 0;
}

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;
}