T1 NEERC2016 Cactus Construction

考虑一棵树怎么做。容易想到，我们保证递归完一棵子树得时候根为 $2$ ，其他内容为 $3$ ，然后当前点 $u$ 设 $1$ ，于是每次就连 $1 \to 2$ 然后把 $2$ 整成 $3$ ，再做下一棵子树即可。这样只需要三种颜色。

考虑仙人掌咋办。还是类似地，我们尝试做完一个环的时候把最上面设置成 $2$ ，这里为了方便，可以类似圆方树把一条边也看成长度为 $2$ 的环。然后考虑类似建立圆方树的过程。如果一个儿子 $v$ 自己为一个环顶（也就是 low[v] == dfn[u]） ，我们来处理这个环。按照弹栈顺序（也就是从深到浅）来做。我们把起始点设置为最深的，为了方便最后连完环上最后一条边把它设置成 $4$ ，然后考虑下一个点，类似树，钦定做完这个子树的时候它的颜色是 $2$ ，子树其他点是 $3$ ，然后把 $2,4$ 连起来，然后把 $2$ 设成 $1$ ，再考虑下一个点的时候就 $2,1$ 连边，然后把 $1$ 变成 $3$ ，把 $2$ 变成 $1$ ，一直这么做即可。最后把 $4,2$ 连起来即可。

可能需要判长度为 $2$ 的环，我的代码多进行了几次无用操作就不需要了，但是操作数略高。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN];

vi G[MAXN];
vi pr[MAXN];

struct tcurts {
	int o , a , c1 , c2;
	tcurts( int o , int a , int c1 , int c2 ) : o(o) , a(a) , c1(c1) , c2(c2) {}
};
vector<tcurts> ops;
void J( int a , int b ) {
	ops.eb( 0 , a , b , 0 );
}
void R( int a , int c1 , int c2 ) {
	ops.eb( 1 , a , c1 , c2 );
}
void C( int a , int c1 , int c2 ) {
	ops.eb( 2 , a , c1 , c2 );
}

int dfn[MAXN] , low[MAXN] , clo , dep[MAXN] , idx[MAXN] , stk[MAXN] , top;
void tarjan( int u , int f ) {
	dfn[u] = low[u] = ++ clo;
	stk[++ top] = u;
	R( u , 1 , 2 );
	for( int v : G[u] ) {
		if( !dfn[v] ) {
			tarjan( v , u );
			low[u] = min( low[u] , low[v] );
			if( low[v] == dfn[u] ) {
				int s = stk[top];
				R( s , 2 , 4 ) , -- top;
				int la = 4 , lu = s;
				if( s != v ) {
					int k;
					do {
						k = stk[top --];
						J( lu , k );
						C( lu , la , 2 );
						R( lu , 1 , 3 );
						R( lu , 2 , 1 );
						la = 1 , lu = k;
					} while( k != v );
				}
				J( u , v );
				C( u , 2 , 1 ) , C( u , 2 , 4 );
				R( u , 4 , 3 ) , R( u , 1 , 3 );
			}
		} else low[u] = min( low[u] , dfn[v] );
	}
}

void solve() {
	cin >> n >> m;
	rep( i , 1 , m ) {
		int k , u , v;
		scanf("%d",&k);
		scanf("%d",&u);
		rep( i , 2 , k ) scanf("%d",&v) , G[u].pb( v ) , G[v].pb( u ) , u = v;
	}
	tarjan( 1 , 1 );
	cout << ops.size() << endl;
	for( auto t : ops ) {
		if( t.o == 0 ) {
			printf("j %d %d\n",t.a,t.c1);
		} else if( t.o == 1 ) {
			printf("r %d %d %d\n",t.a,t.c1,t.c2);
		} else if( t.o == 2 ) {
			printf("c %d %d %d\n",t.a,t.c1,t.c2);
		}
	}
}

signed main() {
// 	freopen("cactus.in","r",stdin) , freopen("cactus.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

HDU5121 Just A Mistake

考虑一个 $dp$ ，设 $dp[u][i]$ 表示 $u$ 子树已经把顺序决定好，钦定 $u$ 最后被加进了独立集，$u$ 为排列中第 $i$ 个位置的方案数。

由于钦定了这个点必须被加入独立集，于是我们考虑对每个点为根进行一次 $dp$ ，最后把所有 $dp$ 加起来就是答案。

转移就是枚举 $v$ 的位置以及 $u$ 的位置，但是发现直接转移还需要枚举一下 $v$ 前面有多少个数在合并后在 $u$ 前面，系数是两个组合数的积。然后需要保证 $u$ 最后在独立集里面，因此必须保证要么 $v$ 没被加进去，要么 $u$ 在 $v$ 前面，这两个条件算起来比较阴间，可以用总方案数量减去 $v$ 在 $u$ 前面的方案数量，即 $v$ 前面合并后在 $u$ 前面的数量必须大于等于 $v$ 的位置。

然后会发现系数只和最后枚举的东西以及 $u$ 的位置有关，于是我们只枚举 $u$ 的位置以及由多少个 $v$ 序列的数被整到了 $u$ 的前面，最后那个系数和 $dp$ 的乘积可以前缀和预处理。

写得比较意识流，建议自己推一下 /kel

最终复杂度 $O(n^3)$ 。代码感觉很阴间，容易写挂。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 236
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
const int P = 1e9 + 7;
typedef long long ll;
int n;
int A[MAXN];

vi G[MAXN];
int wy[MAXN][MAXN] , C[MAXN][MAXN] , J[MAXN];
int tw[MAXN] , siz[MAXN];
void dfs( int u , int f ) {
	siz[u] = 1;
	wy[u][1] = 1;
	for( int v : G[u] ) if( v != f ) {
		dfs( v , u );
		int sz = siz[u] + siz[v];
		rep( i , 1 , siz[u] ) tw[i] = wy[u][i] , wy[u][i] = 0;
		rep( i , 1 , siz[u] ) {
			int ts = J[siz[v]];
			rep( j , 0 , siz[v] ) {
				ts = ( ts + P - wy[v][j] ) % P;
				wy[u][i + j] = ( wy[u][i + j] + ts * 1ll * C[i - 1 + j][j] % P * C[sz - i - j][siz[v] - j] % P * tw[i] ) % P;
			}
		}
		siz[u] = sz;
	}
}

int kase = 0;

void solve() {
	cin >> n;
	rep( i , 1 , n ) G[i].clear();
	rep( i , 2 , n ) {
		int u , v;
		scanf("%d%d",&u,&v);
		G[u].pb( v ) , G[v].pb( u );
	}
	int res = 0;
	rep( i , 1 , n ) {
		rep( j , 1 , n ) rep( k , 1 , n ) wy[j][k] = 0;
		dfs( i , i );
		rep( k , 1 , n ) res = ( res + wy[i][k] ) % P;
//		cout << wy[2][1] << endl;
	}
	++ kase;
	printf("Case #%d: %d\n",kase,res);
}

signed main() {
	rep( i , 0 , MAXN - 1 ) {
		C[i][0] = 1;
		if( i ) J[i] = J[i - 1] * 1ll * i % P;
		else J[i] = 1;
		rep( j , 1 , i ) C[i][j] = ( C[i - 1][j] + C[i - 1][j - 1] ) % P;
	}
    int T;cin >> T;while( T-- ) solve();
//    solve();
}

AUOJ473 简单题

开始以为边分树合并有救，后来发现这题合并的东西或者查询的东西放到边分树就很没救。

对两个图建出 Kruskal 重构树，然后问题变成了求所有点对在两棵树 LCA 权值积的和。

我们可以考虑对第一棵树做一次差分，$c’_u = c_u - c_f$ ，然后对这个树进行树剖。然后在第二棵树上进行 dfs ，再进行线段树合并 + 启发式合并即可。具体来说，我们把每个叶子开个主席树，包括的只有这个叶子加入后一些链会被权值 $+1$ （实际上一棵树的值为所有位置的权值乘上 $c_u$ ）。然后每次合并的时候枚举较小的一侧，分别进行链查询即可。

复杂度 $O(n\log^3n)$ 。

本来想写边分合并，写完发现好像不是很能合并，于是无限期咕咕咕了。。