最大权闭合子图

http://hihocoder.com/problemset/problem/1398

 

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

给你一张DAG,每个点有点权,让你找出一个拓扑序,使得最大连续子段和尽量大。n<=50,-200<=ai<=200

首先显然拓扑序的后缀一定是个闭合子图,那么拓扑序的连续子段其实是两个闭合子图的差。

把每个点拆成两个,具体自行脑补。。

#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;
typedef long double ld;
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;
int nxt[500010],q[500010],S,T,ans,d[500010],hed[500010],cap[500010],too[500010],nedge,n,m,x,y,a[666];
void ae(int x,int y,int w){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
	cap[nedge]=w;
}
void add(int x,int y,int w){
	ae(x,y,w),ae(y,x,0);
}
bool build(){
	int he=0,ta=1;
	q[1]=S;
	FOR(i,S,T) d[i]=-1;
	d[S]=0;
	while (he!=ta){
		int x=q[++he];
		for (int i=hed[x];i;i=nxt[i]){
			int y=too[i];
			if (!cap[i] || d[y]!=-1) continue;
			d[y]=d[x]+1;
			q[++ta]=y;
			if (y==T) return 1;
		}
	}
	return 0;
}
int fnd(int x,int flo){
	if (x==T) return flo;
	int ret,w=0;
	for (int i=hed[x];i && w<flo;i=nxt[i]){
		int y=too[i];
		if (d[y]==d[x]+1 && cap[i] && (ret=fnd(y,min(flo-w,cap[i]))))
			w+=ret,cap[i]-=ret,cap[i^1]+=ret;
	}
	d[x]=-1;
	return w;
}
int dinic(){
	int ans=0;
	while (build()){
		while (1){
			int flo=fnd(S,INF);
			if (!flo) break;
			ans+=flo;
		}
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	S=0;
	T=n+n+1;
	nedge=1;
	FOR(i,1,n){
		getint(a[i]);
		ans+=abs(a[i]);
		if (a[i]>=0) add(S,i,a[i]),add(n+i,T,a[i]);
		else add(i,T,-a[i]),add(S,n+i,-a[i]);
		add(i+n,i,INF);
	}
	FOR(i,1,m){
		getint(x),getint(y);
		add(x,y,INF),add(x+n,y+n,INF);
	}
	cout<<ans-dinic()<<endl;
	return 0;
}

http://codeforces.com/contest/103/submission/33199171

先找出一个完美匹配,然后对于左边的x,匹配右边的match[x],对于右边的y,匹配左边的match'[y].

现在要证明,一个方法是合法的当且仅当:

对于任意选了的左边的x,x连出去的点y必须选了(题目条件);对于任意的选了的y,match'[y]必须也选了。

令左边选的集合为P,右边选的集合为Q。

充分性:根据hall定理,|P|<=|Q|,因为对于任意的x属于Q,match'[x]属于P,所以|P|>=|Q|,所以|P|=|Q|。

必要性:假设选了y,match'[y]没有选(即左边一个点x选了,match[x]没有选),那么一定|P|<|Q|。

假设我在左边,你在右边,因为match互不相同,所以我有一个x,你就有一个match[x],"我有的你都有了,我没有的你也有(MYC原话)“。显然不合法。

之后就是个最大权闭合子图了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<complex>
#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;
bool c[1010][1010],v[5555];
int nxt[500010],q[500010],S,T,ans,h[500010],g[500010],d[500010],hed[500010],cap[500010],too[500010],nedge,n,m,x,y,a[666];
void ae(int x,int y,int w){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
	cap[nedge]=w;
}
void add(int x,int y,int w){
	ae(x,y,w),ae(y,x,0);
}
bool build(){
	int he=0,ta=1;
	q[1]=S;
	FOR(i,S,T) d[i]=-1;
	d[S]=0;
	while (he!=ta){
		int x=q[++he];
		for (int i=hed[x];i;i=nxt[i]){
			int y=too[i];
			if (!cap[i] || d[y]!=-1) continue;
			d[y]=d[x]+1;
			q[++ta]=y;
			if (y==T) return 1;
		}
	}
	return 0;
}
int fnd(int x,int flo){
	if (x==T) return flo;
	int ret,w=0;
	for (int i=hed[x];i && w<flo;i=nxt[i]){
		int y=too[i];
		if (d[y]==d[x]+1 && cap[i] && (ret=fnd(y,min(flo-w,cap[i]))))
			w+=ret,cap[i]-=ret,cap[i^1]+=ret;
	}
	d[x]=-1;
	return w;
}
int dinic(){
	int ans=0;
	while (build()){
		while (1){
			int flo=fnd(S,INF);
			if (!flo) break;
			ans+=flo;
		}
	}
	return ans;
}
bool ck(int x){
	FOR(y,1,n){
		if (!c[x][y] || v[y]) continue;
		v[y]=1;
		if (h[y]==-1 || ck(h[y])){
			h[y]=x;
			return 1;
		}
	}
	return 0;
}
int main(){
	scanf("%d",&n);
	S=0;
	T=n+n+1;
	nedge=1;
	memset(h,-1,sizeof(h));
	FOR(i,1,n){
		scanf("%d",&x);
		while (x--){
			getint(y);
			c[i][y]=1;
		}
	}
	FOR(i,1,n){
		FOR(j,1,n) v[j]=0;
		ck(i);
	}
	FOR(i,1,n) g[h[i]]=i;
	FOR(i,1,n){
		FOR(j,1,n)
			if (c[i][j] && j!=g[i]){
				add(i,h[j],INF);
			}
	}
	FOR(i,1,n){
		getint(a[i]);
		a[i]=-a[i];
		if (a[i]>=0) add(S,i,a[i]),ans+=a[i];
		else add(i,T,-a[i]);
	}
	ans-=dinic();
	cout<<-ans<<endl;
	return 0;
}

另外还有一种做法用到了一个小技巧:化不合法为不优。

你让左边的权+M(M很大),那么左边的点少选一个会带来很”恶劣“的影响使得解很差,不影响你求最优解。

从数据范围推测算法

以下仅对非TC题适用

 

n<=13

3^n*n^2 http://cwystc.is-programmer.com/posts/211162.html

 

n<=100

随机最大团

 

n<=400

最大流 http://cwystc.is-programmer.com/posts/211145.html

 

k<=n<=50

2^(n/2) 暴力 http://cwystc.is-programmer.com/posts/211416.html

根据k的大小写2种不同复杂度的指数级暴力拼起来 http://cwystc.is-programmer.com/posts/211416.html


n<=1e9,k<=100

矩阵乘法 O(logn*k^3) http://cwystc.is-programmer.com/posts/210962.html

 

n<=1e5,k<=12

bitset O(n*2^k/32) http://cwystc.is-programmer.com/posts/211116.html

 

MO=998244353

NTT

 

n=1e10

杜教筛

2-SAT

https://orbitingflea.github.io/2017/08/18/note/2-sat/

 

CF568C

显然2-sat,求出最长的lcp然后再按位确定。

用时成功垫底QAQ

http://codeforces.com/contest/568/submission/32624914

一些不为人知的***

1.

multiset<int> S;

S.erase(x)

会把所有S中的x删除,而不是删除S中的一个x,想要删除一个x,要写S.erase(S.find(x))

2.

NOIP实际时限<=题目上时限*0.4

3.

NOIP模拟题中一些**出题人的强制在线可能是假的(真实比赛估计不会这样)

4.

取模时候用到了减法,最后要(ans+=MO)%=MO

5.

网络流中的双向边,最大流加2条边,费用流要加4条边

6.

注意MO=998244353|1000000007?

7.

(a+=b*c)

a:int b:LL c:int

bomb

8.

struct node{
	LL s;
	int A,B,C,D;
	node(){}
	node(LL _s,int _A,int _B,int _C,int _D){
		s=_s,A=_A,B=_B,C=_C,D=_D;
	}
	bool operator < (const node & T) const{
		return (s<T.s);
	}
};
set<node> S;

这样写set会把所有s相等的node都认为是一样的,进行去重,导致不应该删掉的东西被删掉。

9.

有些题面数据范围是:n*m<=1e5,但是题面有隐含条件n<=m,这时候O(n^2*m)的对的。

10.

树状数组求sum(4)但是add的时候都是n=3,会GG

11.

注意看清MO是998244353|1000000007|1000000009

12.

就算包了bits/stdc++.h,也要using namespace std;

CF101234E

给你一个排列,删掉每个数代价是ci,删掉这个数的同时这个数前面比他大的和这个数后面比他小的也会同时消失,要求花最小代价删光所有数。

首先观察可知,删掉的数形成一个极长上升子序列。

这个就得到了一个简单的O(n^2) DP。

听说可以树套树优化?

考虑分治,用左边的DP值去更新右边的DP值。

首先因为是极大的,所以左边的有用状态肯定是呈现递减状物,而且可以发现每个状态到下一个有用的状态连边,形成了一棵树。

对右边的数在左边找状态去转移的时候,从左边低于他的最高的开始,一直往树上的父亲爬,直到太低了为止,用倍增优化即可,复杂度nlog^2n。

#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;
typedef long double ld;
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;
int n,p[200010],c[200010],dp[200010],f[200010][20],v[200010][20];
int que(int x,int t,int m){
	if (p[x]<=t) return INF;
	int ans=INF;
	FORD(i,19,0)
		if (f[x][i]!=m+1 && p[f[x][i]]>t) ans=min(ans,v[x][i]),x=f[x][i];
	ans=min(ans,v[x][0]);
	return ans;
}
void cdq(int l,int r){
	if (l==r) return;
	int m=l+r>>1;
	cdq(l,m);
	map<int,int> st;
	st[-2]=m+1;
	FOR(i,0,19) f[m+1][i]=m+1,v[m+1][i]=INF;
	FORD(i,m,l){
		int t=(--st.lower_bound(p[i]))->se;
		st[p[i]]=i;
		f[i][0]=t,v[i][0]=dp[i];
		FOR(j,1,19) f[i][j]=f[f[i][j-1]][j-1],v[i][j]=min(v[i][j-1],v[f[i][j-1]][j-1]);
	}
	set<int> ts;
	ts.insert(-2);
	FOR(i,m+1,r){
		int t=*(--ts.lower_bound(p[i]));
		dp[i]=min(dp[i],que((--st.lower_bound(p[i]))->se,t,m)+c[i]);
		ts.insert(p[i]);
	}
	cdq(m+1,r);
}
int main(){
	scanf("%d",&n);
	FOR(i,1,n) getint(p[i]);
	p[n+1]=n+1;
	FOR(i,1,n) getint(c[i]);
	dp[0]=0;
	FOR(i,1,n+1) dp[i]=INF;
	cdq(0,n+1);
	cout<<dp[n+1]<<endl;
	return 0;
}

manacher

//输入,并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] > mx) {
        mx = i + p[i];
        id = i;
    }
}
//找出p[i]中最大的

一个字符串本质不同的回文串只有O(n)个

FFT

http://picks.logdown.com/posts/177631-fast-fourier-transform

 

CF286E

让你构造尽量少的数使得这些数中选出一些数的和(可以重复选同一个数,和<=m)组成的集合与输入的集合那n个数完全相同。n,m<=1e6

首先我们可以注意到构造的数肯定在输入的集合中出现过,即构造的这些数是输入数集的子集。(否则与题意条件矛盾)

所以我们考虑一个naive的做法,按照输入集合的顺序(已经sort好了),从前往后,如果当前这个数已经出现在构造的数能组成的集合中了,就跳过此数,否则把此数加入构造的数集,考虑怎么知道这个数是否已经组出来了,直接背包,获得O(nm)算法。

我们认为一个数如果不加入构造的数集,这个数是没用的。

一个数如果是没用的,说明他可以由另外的数相加得到。

我们来证明这个数最多由2个数相加得到。

如果由3个数相加得到,比如x=a+b+c。

如果输入的集合里有y=a+b,直接用x=y+c即可不需要x=a+b+c,

如果输入的集合里没y=a+b,则组成的y与题意条件矛盾,不合法。

所以一定是由2个构造的数集中的数相加得到。

那么我们只要对于每个ai判断是否存在ai=aj+ak。

显然FFT即可。

无解的判断很简单。

http://codeforces.com/contest/286/submission/31786843

仙人掌-圆方树

圆方树:

http://immortalco.blog.uoj.ac/blog/1955

仙人掌最大独立集

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<complex>
#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;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;
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;
int n,m,x,y,N;
namespace Tree{
	int nedge;
	int n;
	int nxt[500010],f[500010][2],g[500010][2],hed[500010],too[500010];
	void init(){
		memset(hed,0,sizeof(hed));
		nedge=1;
	}
	void ae(int x,int y){
		nxt[++nedge]=hed[x];
		hed[x]=nedge;
		too[nedge]=y;
	}
	/*
	void prin(){
		FOR(x,1,n){
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (x<y) printf("%d %d\n",x,y);
			}
		}
	}
	*/
	void dfs(int x,int l){
		if (x<=N){
			f[x][0]=0,f[x][1]=1;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				dfs(y,x);
				f[x][0]+=max(f[y][0],f[y][1]);
				f[x][1]+=f[y][0];
			}
		}
		else{
			int son=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				dfs(y,x);
			}
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				g[++son][0]=f[y][0];
				g[son][1]=f[y][1];
			}
			FOR(i,2,son){
				g[i][0]+=max(g[i-1][0],g[i-1][1]);
				g[i][1]+=g[i-1][0];
			}
			f[x][1]=max(g[son][0],g[son][1]);
			son=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				g[++son][0]=f[y][0];
				g[son][1]=f[y][1];
			}
			g[1][1]=-INF;
			FOR(i,2,son){
				g[i][0]+=max(g[i-1][0],g[i-1][1]);
				g[i][1]+=g[i-1][0];
			}
			f[x][0]=g[son][0];
		}
	}
}
namespace Cactus{
	int nedge;
	int n,dfs_block=0;
	bool u[500010];
	int nxt[500010],dfn[500010],fa[500010],F[500010],hed[500010],too[500010];
	void init(){
		nedge=1;
		memset(dfn,0,sizeof(dfn));
		sizeof(hed,0,sizeof(hed));
		memset(fa,0,sizeof(fa));
		memset(F,0,sizeof(F));
		memset(u,0,sizeof(u));
	}
	void ae(int x,int y){
		nxt[++nedge]=hed[x];
		hed[x]=nedge;
		too[nedge]=y;
	}
	void dfs(int x,int l){
		dfn[x]=++dfs_block;
		for (int i=hed[x];i;i=nxt[i]){
			int y=too[i];
			if (y==l) continue;
			if (!dfn[y]) fa[y]=x,F[y]=i,dfs(y,x);
			if (dfn[y]>dfn[x]) continue;
			int t=x;
			++Tree::n;
			u[i]=1;
			while (1){
				Tree::ae(t,Tree::n);
				Tree::ae(Tree::n,t);
				if (t==y) break;
				u[F[t]]=1;
				t=fa[t];
			}
		}
	}
	void work(){
		FOR(i,1,nedge) u[i]=0;
		dfs(1,0);
		FOR(i,1,n){
			for (int j=hed[i];j;j=nxt[j]){
				int y=too[j];
				if (u[j] || u[j^1]) continue;
				Tree::ae(i,y);
			}
		}
	}
};
int main(){
	Cactus::init();
	Tree::init();
	scanf("%d%d",&n,&m);
	N=n;
	Cactus::n=n;
	Tree::n=n;
	FOR(i,1,m){
		getint(x),getint(y);
		Cactus::ae(x,y);
		Cactus::ae(y,x);
	}
	Cactus::work();
	Tree::dfs(1,0);
//	Tree::prin();
	printf("%d\n",max(Tree::f[1][0],Tree::f[1][1]));
	return 0;
}

仙人掌直径

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<complex>
#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;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;
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;
int n,m,x,y,ans,N,k,stk[500010];
namespace Tree{
	int nedge;
	int n;
	int nxt[500010],Q[500010],f[500010],hed[500010],too[500010];
	void init(){
		memset(hed,0,sizeof(hed));
		nedge=1;
	}
	void ae(int x,int y){
		nxt[++nedge]=hed[x];
		hed[x]=nedge;
		too[nedge]=y;
	}
	
	void prin(){
		FOR(x,1,n){
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (x<y) printf("%d %d\n",x,y);
			}
		}
	}
	void dfs(int x,int l){
		if (x<=N){
			int mx1=0,mx2=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				dfs(y,x);
				if (f[y]+1>=mx1) mx2=mx1,mx1=f[y]+1;
				else if (f[y]+1>=mx2) mx2=f[y]+1;
			}
			f[x]=mx1;
			ans=max(ans,mx1+mx2);
		}
		else{
			int top=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				dfs(y,x);
				++top;
			}
			int cnt=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				++cnt;
				stk[cnt]=y;
				f[x]=max(f[x],f[y]+min(cnt-1,top-cnt));
			}
			/*
			FOR(i,1,top)
				FOR(j,i+1,top)
					ans=max(ans,f[stk[i]]+f[stk[j]]+min(j-i,i+top+1-j));
			*/
			stk[++top]=0;
			FOR(i,1,cnt) stk[++top]=stk[i];
			int l=1,r=0;
			FOR(i,1,(cnt+1)/2){
				while (l<=r && f[stk[i]]-i>=f[stk[Q[r]]]-Q[r]) --r;
				Q[++r]=i;
			}
			for (int p=1,q=(cnt+1)/2+1;p<=cnt;++p,++q){
				while (Q[l]<p) ++l;
				ans=max(ans,q-Q[l]+f[stk[q]]+f[stk[Q[l]]]);
				while (l<=r && f[stk[q]]-q>=f[stk[Q[r]]]-Q[r]) --r;
				Q[++r]=q;
			}
		}
	}
}
namespace Cactus{
	int nedge;
	int n,dfs_block=0;
	bool u[500010];
	int nxt[500010],dfn[500010],fa[500010],F[500010],hed[500010],too[500010];
	void init(){
		nedge=1;
		memset(dfn,0,sizeof(dfn));
		sizeof(hed,0,sizeof(hed));
		memset(fa,0,sizeof(fa));
		memset(F,0,sizeof(F));
		memset(u,0,sizeof(u));
	}
	void ae(int x,int y){
		nxt[++nedge]=hed[x];
		hed[x]=nedge;
		too[nedge]=y;
	}
	void dfs(int x,int l){
		dfn[x]=++dfs_block;
		for (int i=hed[x];i;i=nxt[i]){
			int y=too[i];
			if (y==l) continue;
			if (!dfn[y]) fa[y]=x,F[y]=i,dfs(y,x);
			if (dfn[y]>dfn[x]) continue;
			int t=x;
			++Tree::n;
			u[i]=1;
			while (1){
				Tree::ae(t,Tree::n);
				Tree::ae(Tree::n,t);
				if (t==y) break;
				u[F[t]]=1;
				t=fa[t];
			}
		}
	}
	void work(){
		FOR(i,1,nedge) u[i]=0;
		dfs(1,0);
		FOR(i,1,n){
			for (int j=hed[i];j;j=nxt[j]){
				int y=too[j];
				if (u[j] || u[j^1]) continue;
				Tree::ae(i,y);
			}
		}
	}
};
int main(){
	Cactus::init();
	Tree::init();
	scanf("%d%d",&n,&m);
	N=n;
	Cactus::n=n;
	Tree::n=n;
	FOR(i,1,m){
		getint(k);
		FOR(j,1,k) getint(stk[j]);
		FOR(j,2,k) Cactus::ae(stk[j-1],stk[j]),Cactus::ae(stk[j],stk[j-1]);
	}
	Tree::f[0]=-INF;
	Cactus::work();
//	Tree::prin();
	Tree::dfs(1,0);
	cout<<ans<<endl;
	return 0;
}

卡特兰数

普及了一些卡特兰数的知识。

接下来尝试解决一个问题。

求有多少长度为2n的01串满足任何非空前缀0的数量都不等于1的数量。

首先考虑对于第一位,选0和选1方案数是一样的,最后再*2就可以了。

假设第一位是1,那么对于后面的2n-1位,只要满足任何前缀1的数量>=0的数量。

假设后面的2n-1位中有m个0(m<=2n-1-m,0<=m<=n-1),

那么根据上面得到的东西,方案数是C(2n-1,m)-C(2n-1,m-1)

所以总的是

sigma(C(2n-1,m)-C(2n-1,m-1)) (m=0..n-1)

然后相同的项都抵消了剩下

=C(2n-1,n-1)

最后乘2

C(2n-1,n-1)*2=C(2n-1,n-1)+C(2n-1,n)=C(2n,n)

树链求交

void ae(int x,int y){
    nxt[++nedge]=hed[x];
    hed[x]=nedge;
    too[nedge]=y;
}
void lca_init(){
    FOR(i,1,n) mx=max(mx,dep[i]);
    mx=log2(mx);
    FOR(j,1,mx)
        FOR(i,1,n)
            anc[i][j]=anc[anc[i][j-1]][j-1];
}
int lca(int x,int y){
    if (dep[x]>dep[y]) swap(x,y);
    FORD(i,mx,0)
        if (dep[y]-(1<<i)>=dep[x]) y=anc[y][i];
    if (x==y) return x;
    FORD(i,mx,0)
        if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return anc[x][0];
}
pa intersect(int x,int y,int p,int q){
    int s=lca(x,p),t=lca(y,q);
    if (dep[s]<dep[y] || dep[s]<dep[q]) return mp(0,0);
    return mp(s,y+q-t);
}
pa chainintersect(int x,int y,int p,int q){
    int z=lca(x,y),r=lca(p,q);
    pa chain[4],inter[2];
    chain[0]=intersect(x,z,p,r);
    chain[1]=intersect(x,z,q,r);
    chain[2]=intersect(y,z,p,r);
    chain[3]=intersect(y,z,q,r);
    int num=0;
    FOR(i,0,3)
        if (chain[i].fi!=chain[i].se) inter[num++]=chain[i];
    if (!num){
        FOR(i,0,3)
            if (chain[i].fi) return chain[i];
        return mp(0,0);
    }
    if (num==1) return inter[0];
    if (inter[0].fi==inter[1].fi) return mp(inter[0].se,inter[1].se);
    else if (inter[0].fi==inter[1].se) return mp(inter[0].se,inter[1].fi);
    else if (inter[0].se==inter[1].fi) return mp(inter[0].fi,inter[1].se);
    else return mp(inter[0].fi,inter[1].fi);
}
void mkt(int x,int l){
    dep[x]=dep[l]+1;
    anc[x][0]=l;
    for (int i=hed[x];i;i=nxt[i]){
        int y=too[i];
        if (y==l) continue;
        mkt(y,x);
    }
}