ztr的多项式板子

namespace poly{
    struct AwD{int x;AwD(){x=0;}AwD(int _x){x=_x;}};
    AwD operator+(AwD a,AwD b){return (AwD){(a.x+b.x)%mo};}
    AwD operator-(AwD a,AwD b){return (AwD){(a.x-b.x+mo)%mo};}
    AwD operator*(AwD a,AwD b){return (AwD){(int)(1LL*a.x*b.x%mo)};}
    AwD operator^(AwD a,int b){if(!b) return (AwD){1};AwD temp=a^(b>>1);temp=temp*temp;if(b&1) temp=temp*a;return temp;}
    AwD operator/(AwD a,AwD b){return a*(b^(mo-2));}
    const AwD root=(AwD){3};
    void ntt(AwD*a,int n,int d){
        int i,j,k;
        AwD w,t,u,v;
        for(i=(n>>1),j=1;j<n;j++){
            if(i<j) t=a[i],a[i]=a[j],a[j]=t;
            for(k=(n>>1);i&k;i^=k,k>>=1);i^=k;
        }
        for(k=2;k<=n;k<<=1){
            w=root^((mo-1)/k*(k-d));
            for(i=0;i<n;i+=k){
                t=(AwD){1};
                for(j=i;j<i+(k>>1);j++){
                    u=a[j];v=t*a[j+(k>>1)];
                    a[j]=u+v;a[j+(k>>1)]=u-v;t=t*w;
                }
            }
        }
    }
    AwD a[N],b[N];
    void print(AwD*a,int l){
        for(int i=0;i<l;i++) printf("%d ",a[i].x);
        printf("\n");
    }
    void plus(AwD*_a,AwD*_b,int l,AwD*c){
        for(int i=0;i<l;i++) a[i]=_a[i],b[i]=_b[i];
        for(int i=0;i<l;i++) c[i]=a[i]+b[i];
    }
    void subt(AwD*_a,AwD*_b,int l,AwD*c){
        for(int i=0;i<l;i++) a[i]=_a[i],b[i]=_b[i];
        for(int i=0;i<l;i++) c[i]=a[i]-b[i];
    }
    void mult(AwD*_a,AwD b,int l,AwD*c){
        for(int i=0;i<l;i++) a[i]=_a[i];
        for(int i=0;i<l;i++) c[i]=a[i]*b;
    }
    void mult(AwD*_a,AwD*_b,int l,AwD*c){
        for(int i=0;i<l;i++) a[i]=_a[i],b[i]=_b[i];
        ntt(a,l,1);ntt(b,l,1);
        for(int i=0;i<l;i++) c[i]=a[i]*b[i];
        ntt(c,l,-1);
        AwD tmp=1/(AwD){l};
        for(int i=0;i<l;i++) c[i]=c[i]*tmp;
    }
    AwD a1[N],aa[N],tmp[N];
    void inv(AwD*_a,int l,AwD*b){   
        for(int i=0;i<l;i++) a1[i]=_a[i];
        for(int i=0;i<l;i++) b[i]=i?(AwD){0}:a1[i]^(mo-2);
        for(int l0=2;l0<=l;l0<<=1){
            mult(b,(AwD){2},l0>>1,tmp);
            mult(b,b,l0,b);
            for(int i=0;i<(l0<<1);i++) aa[i]=i<l0?a1[i]:(AwD){0};
            mult(aa,b,l0<<1,b);
            for(int i=l0;i<(l0<<1);i++) b[i]=(AwD){0};
            subt(tmp,b,l0,b);
        }
    }
}

欧拉回路

http://uoj.ac/submission/219661

http://uoj.ac/submission/219665

 

LCT

BZOJ2157

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int INF=1e9+10;
struct node{
	int ch[2],fa,v,mx,mn,s;
	int tgx,tgy;
	bool rev;
	node(){tgx=1;}
}t[200010];
int n,m,stk[200010],top,x,y,w;
char s[666];
bool isroot(int x){
	return (t[t[x].fa].ch[0]!=x && t[t[x].fa].ch[1]!=x);
}
void pushup(int x){
	t[x].s=0;
	t[x].mx=-INF;
	t[x].mn=INF;
	if (x>n){
		t[x].s=t[x].v;
		t[x].mx=max(t[x].mx,t[x].v);
		t[x].mn=min(t[x].mn,t[x].v);
	}
	FOR(i,0,1)
		if (t[x].ch[i]){
			t[x].mx=max(t[t[x].ch[i]].mx,t[x].mx);
			t[x].mn=min(t[t[x].ch[i]].mn,t[x].mn);
			t[x].s+=t[t[x].ch[i]].s;
		}
}
void TAG(int x,int p,int q){
	t[x].v=t[x].v*p+q;
	t[x].s=t[x].s*p+q;
	if (t[x].mx>=t[x].mn){
		t[x].mx=t[x].mx*p+q;
		t[x].mn=t[x].mn*p+q;
		if (t[x].mx<t[x].mn) swap(t[x].mx,t[x].mn);
	}
	//(*x+y)*p+q
	t[x].tgx*=p;
	t[x].tgy=t[x].tgy*p+q;
}
void REV(int x){
	swap(t[x].ch[0],t[x].ch[1]);
	t[x].rev^=1;
}
void pushdown(int x){
	if (t[x].rev){
		if (t[x].ch[0]) REV(t[x].ch[0]);
		if (t[x].ch[1]) REV(t[x].ch[1]);
		t[x].rev=0;
	}
	if (t[x].tgx!=1 || t[x].tgy!=0){
		if (t[x].ch[0]) TAG(t[x].ch[0],t[x].tgx,t[x].tgy);
		if (t[x].ch[1]) TAG(t[x].ch[1],t[x].tgx,t[x].tgy);
		t[x].tgx=1,t[x].tgy=0;
	}
}
void rot(int x){
	int fa=t[x].fa;
	int gfa=t[fa].fa;
	int t1=(x!=t[fa].ch[0]);
	int t2=(fa!=t[gfa].ch[0]);
	int ch=t[x].ch[t1^1];
	if (!isroot(fa)) t[gfa].ch[t2]=x;
	t[ch].fa=fa;
	t[x].fa=gfa;
	t[x].ch[t1^1]=fa;
	t[fa].fa=x;
	t[fa].ch[t1]=ch;
	pushup(fa);
	pushup(x);
}
void splay(int x){
	stk[top=1]=x;
	int y=x;
	while (!isroot(y)) stk[++top]=t[y].fa,y=t[y].fa;
	FORD(rp,top,1) pushdown(stk[rp]);
	while (!isroot(x)){
		int fa=t[x].fa;
		int gfa=t[fa].fa;
		if (!isroot(fa))
			(x==t[fa].ch[0]^fa==t[gfa].ch[0])?rot(x):rot(fa);
		rot(x);
	}
}
void access(int x){
	int te=0;
	while (x){
		splay(x);
		t[x].ch[1]=te;
		pushup(x);
		te=x;
		x=t[x].fa;
	}
}
void makeroot(int x){
	access(x);
	splay(x);
	REV(x);
}
void link(int x,int y){
	makeroot(x);
	t[x].fa=y;
}

int main(){
	scanf("%d",&n);
	m=n;
	FOR(i,1,n-1){
		getint(x),getint(y),getint(w);
		++x,++y;
		t[++m].v=w;
		t[m].mx=t[m].mn=t[m].s=w;
		link(m,x),link(m,y);
	}
	scanf("%d",&m);
	while (m--){
		scanf("%s",s);
		if (s[0]=='C'){
			getint(x),getint(y);
			x+=n;
			makeroot(x);
			access(x);
			splay(x);
			TAG(x,1,y-t[x].v);
		}
		else if (s[0]=='N'){
			getint(x),getint(y);
			++x,++y;
			makeroot(x);
			access(y);
			splay(y);
			TAG(y,-1,0);
		}
		else if (s[0]=='S'){
			getint(x),getint(y);
			++x,++y;
			makeroot(x);
			access(y);
			splay(y);
			printf("%d\n",t[y].s);
		}
		else if (s[1]=='A'){
			getint(x),getint(y);
			++x,++y;
			makeroot(x);
			access(y);
			splay(y);
			printf("%d\n",t[y].mx);
		}
		else{
			getint(x),getint(y);
			++x,++y;
			makeroot(x);
			access(y);
			splay(y);
			printf("%d\n",t[y].mn);
		}
	}
	return 0;
}

http://codeforces.com/contest/763/submission/34110258

带平衡树代码容易写错的一个地方:写t[xx].yy的时候可能中途旋转了,所以要开个临时变量记下。

http://codeforces.com/contest/603/submission/34171363

维护树的size的时候,要记w,sz分别表示LCT中子树的非重儿子size、总size。

然后在cut,link,access的时候要多写几句话。

注意link,为了使得x接到y上去的时候y的祖先不需要pushup,所以要让y没有父亲,即access(y),splay(y)

李超线段树

BZOJ1568

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
double ans,tagk[500010],S,P,tagb[500010];
bool flag[500010];
char s[666];
int n,x,T;
double crs(double k1,double b1,double k2,double b2){
	return (b2-b1)/(k1-k2);
}
void ins(int l,int r,int rt,double K,double B){
	if (!flag[rt]){
		flag[rt]=1;
		tagk[rt]=K;
		tagb[rt]=B;
		return;
	}
	int m=l+r>>1;
	double f1=K*l+B,f2=tagk[rt]*l+tagb[rt],f3=K*r+B,f4=tagk[rt]*r+tagb[rt];
	if (f2>=f1 && f4>=f3) return;
	if (f1>=f2 && f3>=f4){
		tagk[rt]=K,tagb[rt]=B;
		return;
	}
	double t=crs(K,B,tagk[rt],tagb[rt]);
	if (f1>=f2){
		if (t<=m){
			ins(l,m,rt<<1,K,B);
		}
		else{
			ins(m+1,r,rt<<1|1,tagk[rt],tagb[rt]);
			tagk[rt]=K,tagb[rt]=B;
		}
	}
	else{
		if (t<=m){
			ins(l,m,rt<<1,tagk[rt],tagb[rt]);
			tagk[rt]=K,tagb[rt]=B;
		}
		else{
			ins(m+1,r,rt<<1|1,K,B);
		}
	}
}
void que(int l,int r,int rt,int x){
	ans=max(ans,tagk[rt]*x+tagb[rt]);
	if (l==r) return;
	int m=l+r>>1;
	if (x<=m) que(l,m,rt<<1,x);
	else que(m+1,r,rt<<1|1,x);
}
int main(){
	T=50000;
	scanf("%d",&n);
	FOR(i,1,n){
		scanf("%s",s);
		if (s[0]=='Q'){
			getint(x);
			ans=0.0;
			que(1,T,1,x);
			printf("%lld\n",(long long)(ans/100));
		}
		else{
			scanf("%lf%lf",&S,&P);
			ins(1,T,1,P,S-P);
		}
	}
	return 0;
}

树套树

BZOJ3196,T了一点

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int INF=1e9+10;
struct node{
	int v,siz,cnt;
	int ch[2],fa;
}t[2000010];
int a[200010],tp,n,X,Y,m,ans,x,tot,rt[200010],l,r,k;
void debug(int x){
	if (t[x].ch[0]) debug(t[x].ch[0]);
	FOR(i,1,t[x].cnt) printf("%d ",t[x].v);
	if (t[x].ch[1]) debug(t[x].ch[1]);
}
void DEBUG(){
	FOR(i,1,n) debug(rt[i]),puts("");
	puts("**");
}
void pushup(int x){
	t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].cnt;
}
void rot(int x){
	int fa=t[x].fa;
	int gfa=t[fa].fa;
	int t1=(x!=t[fa].ch[0]);
	int t2=(fa!=t[gfa].ch[0]);
	int ch=t[x].ch[t1^1];
	if (gfa) t[gfa].ch[t2]=x;
	t[ch].fa=fa;
	t[x].fa=gfa;
	t[x].ch[t1^1]=fa;
	t[fa].fa=x;
	t[fa].ch[t1]=ch;
	pushup(fa);
	pushup(x);
}
void splay(int x,int too){
	while (t[x].fa!=too){
		int fa=t[x].fa;
		int gfa=t[fa].fa;
		if (gfa!=too)
			(x==t[fa].ch[0]^fa==t[gfa].ch[0])?rot(x):rot(fa);
		rot(x);
	}
}
int fnd(int x,int k){
	if (k<=t[t[x].ch[0]].siz) return fnd(t[x].ch[0],k);
	else if (k>t[t[x].ch[0]].siz+t[x].cnt) return fnd(t[x].ch[1],k-t[t[x].ch[0]].siz-t[x].cnt);
	else return x;
}
int rnk(int x,int k){
	if (!x) return 0;
	if (k<t[x].v) return rnk(t[x].ch[0],k);
	else if (k==t[x].v) return t[t[x].ch[0]].siz+t[x].cnt;
	else return t[t[x].ch[0]].siz+t[x].cnt+rnk(t[x].ch[1],k);
}
void ins(int &x,int v,int fa){
	if (!x){
		x=++tot;
		t[x].v=v;
		t[x].siz=t[x].cnt=1;
		t[x].fa=fa;
		return;
	}
	if (v==t[x].v) ++t[x].cnt;
	else if (v<t[x].v) ins(t[x].ch[0],v,x);
	else ins(t[x].ch[1],v,x);
	pushup(x);
}
void del(int x,int v){
	X=fnd(rt[x],rnk(rt[x],v-1));
	Y=fnd(rt[x],rnk(rt[x],v)+1);
	splay(X,0);
	rt[x]=X;
	splay(Y,X);
	--t[t[Y].ch[0]].cnt;
	pushup(t[Y].ch[0]);
	if (t[t[Y].ch[0]].cnt==0) t[Y].ch[0]=0;
	pushup(Y);
	pushup(X);
}
inline int lowbit(int x){
	return x&-x;
}
void ADD(int x,int T){
	for (;x<=n;x+=lowbit(x)){
		int tt=tot;
		ins(rt[x],T,0);
		if (tt!=tot){
			rt[x]=tot;
			splay(tot,0);
		}
	}
}
void DEL(int x,int t){
	for (;x<=n;x+=lowbit(x)){
		del(x,t);
	}
}
int SUM(int x,int t){
	int s=0;
	for (;x;x-=lowbit(x))
		s+=rnk(rt[x],t)-1;
	return s;
}
int main(){
//	freopen("t.in","r",stdin);
//	freopen("t.out","w",stdout);
	scanf("%d%d",&n,&m);
	FOR(i,1,n){
		rt[i]=++tot;
		t[rt[i]].v=-INF;
		t[rt[i]].ch[1]=++tot;
		t[tot].v=INF;
		t[tot].fa=tot-1;
		t[tot].cnt=t[tot].siz=1;
		t[tot-1].siz=1;
		t[tot-1].cnt=1;
		pushup(tot-1);
	}
	FOR(i,1,n) getint(a[i]),ADD(i,a[i]);
	while (m--){
		getint(tp);
		if (tp==1){
			getint(l),getint(r),getint(k);
			ans=(SUM(r,k-1)-SUM(l-1,k-1))+1;
			printf("%d\n",ans);
		}
		else if (tp==2){
			getint(l),getint(r),getint(k);
			int L=0,R=1e8;
			while (L<R){
				int O=L+R>>1;
				if (SUM(r,O)-SUM(l-1,O)>=k) R=O;
				else L=O+1;
			}
			printf("%d\n",R);
		}
		else if (tp==3){
			getint(x),getint(k);
			DEL(x,a[x]);
			a[x]=k;
			ADD(x,a[x]);
		}
		else if (tp==4){
			getint(l),getint(r),getint(k);
			k=SUM(r,k-1)-SUM(l-1,k-1);
			int L=0,R=1e8;
			while (L<R){
				int O=L+R>>1;
				if (SUM(r,O)-SUM(l-1,O)>=k) R=O;
				else L=O+1;
			}
			printf("%d\n",R);
		}
		else{
			getint(l),getint(r),getint(k);
			k=SUM(r,k)-SUM(l-1,k)+1;
			int L=0,R=1e8;
			while (L<R){
				int O=L+R>>1;
				if (SUM(r,O)-SUM(l-1,O)>=k) R=O;
				else L=O+1;
			}
			printf("%d\n",R);
		}
	}
	return 0;
}

http://codeforces.com/contest/785/submission/34064644

特技:不要从小往大insert,random_shuffle之后再insert

斯特林数

TCO2014_Wildcard_750

g[i]表示n行i列的答案然后直接容斥即可。

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;
const int MO=1e9+7;
int n,m,c;
LL S[4010][4010],f[4010],g[4010];
class CountTables{
	public:
	int howMany(int N, int M, int C){
		n=N,m=M,c=C;
		S[0][0]=1;
		FOR(i,1,m){
			S[i][0]=0;
			FOR(j,1,i) S[i][j]=(S[i-1][j-1]+S[i-1][j]*j)%MO;
		}
		LL x=1;
		FOR(i,1,m){
			x=x*c%MO;
			f[i]=1;
			FORD(j,x,x-n+1) f[i]=f[i]*j%MO;
			g[i]=f[i];
			FOR(j,1,i-1) (g[i]-=S[i][j]*g[j]%MO)%=MO;
		}
		(g[m]+=MO)%=MO;
		return (int)g[m];
	}
}cwy;

AC自动机

板子

http://192.168.45.99/problem.php?id=1623

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int cnt[500010],q[500010],fail[500010],n,m,x,son[500010][26],tot;
char s[500010];
LL ans;
void ins(){
    x=0;
    FOR(i,0,m-1){
        if (!son[x][s[i]-'a']) son[x][s[i]-'a']=++tot;
        x=son[x][s[i]-'a'];
    }
    cnt[x]=1;
}
void build(){
    int he=0,ta=1;
    q[1]=0;
    while (he!=ta){
        int x=q[++he];
        cnt[x]+=cnt[fail[x]];
        FOR(i,0,25){
            int y=son[x][i];
            if (!y) continue;
            if (x){
                int tmp=fail[x];
                while (tmp && !son[tmp][i]) tmp=fail[tmp];
                fail[y]=son[tmp][i];
            }
            q[++ta]=y;
        }
    }
}
void fnd(){
    x=0;
    FOR(i,0,m-1){
        while (x && !son[x][s[i]-'a']) x=fail[x];
        if (son[x][s[i]-'a']) x=son[x][s[i]-'a'];
        ans+=cnt[x];
    }
}
int main(){
    scanf("%d",&n);
    FOR(i,1,n){
        scanf("%s",s);
        m=strlen(s);
        ins();
    }
    build();
    scanf("%s",s);
    m=strlen(s);
    fnd();
    cout<<ans<<endl;
    return 0;
}

基础练习题

http://codeforces.com/contest/86/submission/33919169

http://codeforces.com/contest/163/submission/33955397

http://codeforces.com/contest/696/submission/33960564

 

http://codeforces.com/contest/547/submission/34041438

每个串可以看成是它的所有的前缀,fail树上能走到k的是合法的,转化为静态二维数点。

CF710F强在AC自动机(留坑

splay

复习splay

http://codeforces.com/contest/38/submission/33897822

http://www.lydsy.com/JudgeOnline/problem.php?id=3786

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
struct node{
	int tp,d,fa;
	int ch[2],siz;
	LL s,v,tag;
}t[200010];
char s[55];
int rt,stk[500010],top,x,y,X,Y,nxt[500010],hed[500010],too[500010],nedge,n,m,a[100010],L[100010],R[100010],dfn,tot;
void ae(int x,int y){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
}
bool isroot(int x){
	return (t[x].fa==0);
}
void dfs(int x,int l){
	L[x]=++dfn;
	t[L[x]].v=a[x];
	t[L[x]].tp=1;
	for (int i=hed[x];i;i=nxt[i]){
		int y=too[i];
		if (y==l) continue;
		dfs(y,x);
	}
	R[x]=++dfn;
	t[R[x]].v=-a[x];
	t[R[x]].tp=-1;
}
void TAG(int x,LL y){
	t[x].v+=t[x].tp*y;
	t[x].s+=t[x].d*y;
	t[x].tag+=y;
}
void pushup(int x){
	t[x].s=t[x].v+t[t[x].ch[0]].s+t[t[x].ch[1]].s;
	t[x].d=t[x].tp+t[t[x].ch[0]].d+t[t[x].ch[1]].d;
	t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
}
void pushdown(int x){
	if (t[x].tag){
		if (t[x].ch[0]) TAG(t[x].ch[0],t[x].tag);
		if (t[x].ch[1]) TAG(t[x].ch[1],t[x].tag);
		t[x].tag=0;
	}
}
void debug(int x){
	pushdown(x);
	if (t[x].ch[0]) debug(t[x].ch[0]);
	printf("%lld ",t[x].v);
	if (t[x].ch[1]) debug(t[x].ch[1]);
}
int build(int l,int r,int fa){
	int m=l+r>>1;
	t[m].s=t[m].v;
	t[m].fa=fa;
	if (l<=m-1) t[m].ch[0]=build(l,m-1,m);
	if (m+1<=r) t[m].ch[1]=build(m+1,r,m);
	pushup(m);
	return m;
}
void rot(int x){
	int fa=t[x].fa;
	int gfa=t[fa].fa;
	int t1=(x!=t[fa].ch[0]);
	int t2=(fa!=t[gfa].ch[0]);
	int ch=t[x].ch[t1^1];
	if (!isroot(fa)) t[gfa].ch[t2]=x;
	t[ch].fa=fa;
	t[x].fa=gfa;
	t[x].ch[t1^1]=fa;
	t[fa].fa=x;
	t[fa].ch[t1]=ch;
	pushup(fa);
	pushup(x);
}
void splay(int x,int too){
	if (too==0) rt=x;
	if (too==-1) too=rt;
	stk[top=1]=x;
	int y=x;
	while (!isroot(y)) stk[++top]=t[y].fa,y=t[y].fa;
	FORD(rp,top,1) pushdown(stk[rp]);
	while (t[x].fa!=too){
		int fa=t[x].fa;
		int gfa=t[fa].fa;
		if (gfa!=too)
			x==t[fa].ch[0]^fa==t[gfa].ch[0]?rot(x):rot(fa);
		rot(x);
	}
}
int rnk(int x){
	splay(x,0);
//	debug(rt),puts("");
	return t[t[x].ch[0]].siz+1;
}
int fnd(int x,int k){
	if (x==-1) x=rt;
//	debug(rt),puts("");
	if (t[t[x].ch[0]].siz>=k) return fnd(t[x].ch[0],k);
	else if (k==t[t[x].ch[0]].siz+1) return x;
	else return fnd(t[x].ch[1],k-t[t[x].ch[0]].siz-1);
}
int main(){
//	freopen("t.in","r",stdin);
//	freopen("t.out","w",stdout);
	scanf("%d",&n);
	FOR(i,2,n){
		int t;
		getint(t);
		ae(t,i);
	}
	FOR(i,1,n) getint(a[i]);
	dfs(1,0);
	tot=dfn;
	rt=build(1,tot,0);
	t[tot+1].ch[1]=tot+2;
	t[tot+2].fa=tot+1;
	t[tot+2].ch[0]=rt;
	t[rt].fa=tot+2;
	rt=tot+1;
	scanf("%d",&m);
//	debug(rt),puts("");
	while (m--){
		scanf("%s",s);
	//	debug(rt),puts("");
		if (s[0]=='Q'){
			getint(x);
		//	debug(rt),puts("");
			int h=fnd(-1,rnk(L[x])+1);
		//	debug(rt),puts("");
			splay(h,0);
			pushdown(rt);
			printf("%lld\n",t[t[h].ch[0]].s);
		}
		else if (s[0]=='F'){
			getint(x),getint(y);
			X=fnd(-1,rnk(L[x])-1);
			Y=fnd(-1,rnk(R[x])+1);
			splay(X,0);
			splay(Y,-1);
		//	debug(rt),puts("");
			TAG(t[t[rt].ch[1]].ch[0],y);
			pushdown(rt);
			pushdown(t[rt].ch[1]);
			pushup(t[rt].ch[1]);
			pushup(rt);
		}
		else{
			getint(x),getint(y);
			X=fnd(-1,rnk(L[x])-1);
			Y=fnd(-1,rnk(R[x])+1);
			splay(X,0);
			splay(Y,-1);
		//	debug(rt),puts("");
			int w=t[t[rt].ch[1]].ch[0];
			t[t[w].fa].ch[0]=0;
			pushup(t[w].fa);
			pushup(rt);
		//	debug(rt),puts("");
			X=fnd(-1,rnk(L[y]));
			Y=fnd(-1,rnk(L[y])+1);
			splay(X,0);
			splay(Y,-1);
		//	debug(rt),puts("");
			t[Y].ch[0]=w;
			t[w].fa=Y;
			pushup(Y);
			pushup(X);
		}
	}
	return 0;
}

生成树计数-基尔霍夫定理

http://vfleaking.blog.163.com/blog/static/1748076342013112523651955/

https://www.cnblogs.com/GerynOhenz/p/4450417.html

http://blog.csdn.net/werkeytom_ftd/article/details/60766200

 

生成树计数-prufer

https://www.cnblogs.com/dirge/p/5503289.html

BZOJ1005

确定每个点度数后容易求出有多少种不同的无根树。

https://loj.ac/problem/6044

硬点一些点作为奇层点,一些点作为偶层层,方案数为C(n-1,k-1)。

令S(x,y)表示左边x个点右边y个点的二分图的生成树计数。

ans=C(n-1,k-1)*S(k,n-k)

考虑用prufer推S(x,y):

最后剩下的两个点肯定一个是左边的,一个是右边的。

因为我们已经确定了左边x个点的标号和右边y个点的标号,所以我们进行求prufer序列这个操作的时候,每次删掉的点是哪一个是确定的,只要考虑写入prufer的数是哪个,如果是删除左边,那么prufer中新增的数有y-1种可能,如果是删除右边,那么prufer中新增的数有x-1种可能,所以S(x,y)=x^(y-1)*y^(x-1)。

https://loj.ac/submission/52865