AT4352 [ARC101C] Ribbons on Tree

When attempting standard subtree DP to match points inside and outside subtrees, the complexity reaches (O(n^3)). However, an alternative approach using inclusion-exclusion principle can be applied by fixing certain edges that must remain uncovered. This transforms the problem into calculating the product of arbitrary pairing schemes across multiple connected components.

For a connected component of size (n) (where (n) is even), the number of arbitrary matching schemes is:

[g_n=\prod_{i=1}^{\frac{n}{2}} (2i-1) ]

Dynamic programming can optimize this inclusion-exclusion process. During transitions, maintain inclusion-exclusion coefficients where (f_{u,i}) represents the current component containing node (u) with size (i). Transitions can be performed through direct convolution.

#include <cstdio>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin)),p1==p2?EOF:*p1++)
#pragma GCC optimize(2,3,"Ofast")
using namespace std
char buf[1<<22],*p1=buf,*p2=buf;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int MAXN = 5003;
const int MOD = 1000000007;
int head[MAXN],to[MAXN<<1],next[MAXN<<1],edge_cnt;
void insert_edge(int u,int v){next[++edge_cnt]=head[u];head[u]=edge_cnt;to[edge_cnt]=v;}
int dp[MAXN][MAXN],factorial[MAXN],size[MAXN],temp[MAXN],node_count;
void tree_dp(int u,int parent){
	size[u]=1;dp[u][1]=1;
	for(int i=head[u],v;i;i=next[i])
		if((v=to[i])^parent){
			tree_dp(v,u);
			for(int j=0;j<=size[u];++j) temp[j]=dp[u][j],dp[u][j]=0;
			for(int j=1;j<=size[u];++j)
				for(int k=0;k<=size[v];++k)
					dp[u][j+k]=(dp[u][j+k]+1ll*temp[j]*dp[v][k])%MOD;
			size[u]+=size[v];
		}
	for(int i=2;i<=size[u];i+=2)
		dp[u][0]=(dp[u][0]-1ll*factorial[i]*dp[u][i]%MOD+MOD)%MOD;	
}
int main(){
	node_count=read();
	for(int i=1;i<node_count;++i){
		int u=read(),v=read();
		insert_edge(u,v);insert_edge(v,u);
	}
	factorial[0]=1;for(int i=2;i<=node_count;i+=2) factorial[i]=1ll*factorial[i-2]*(i-1)%MOD;
	tree_dp(1,0);
	printf("%d\n",MOD-dp[1][0]);
	return 0;
}

[CTS2019]氪金手游

Consider transforming probability calculations on trees through inclusion-exclusion principles. While individual selection probabilities (W_i) appear independent, direct application leads to incorrect results.

The fractional form (\frac{W_i}{\sum_j W_j}) lacks linearity, necessitating denominator compression into DP states using similar techniques from the previous problem.

Reinterpreting the problem reveals the original graph as a weakly connected tree. For an outward-directed tree, the probability that the root node is selected first equals (\frac{Pr(u)}{\sum_{v\in subtree(u)} Pr(v)}), which aligns with practical interpretation and series calculations.

Reverse edges are incorporated through inclusion-exclusion, multiplying coefficients during tree DP transitions.

#include <cstdio>
using namespace std
const int NODE_LIMIT = 6003;
const int VALUE_LIMIT = 3000003;
const int PRIME = 998244353;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
int modular_inverse[VALUE_LIMIT],total_nodes,result;
int memo[NODE_LIMIT][NODE_LIMIT*3],buffer[NODE_LIMIT*3];
int prob[NODE_LIMIT][4];
int probability[NODE_LIMIT],subtree_size[NODE_LIMIT];
int adjacency[NODE_LIMIT],destination[NODE_LIMIT<<1],link[NODE_LIMIT<<1],edge_counter;
bool edge_direction[NODE_LIMIT<<1];
void add_link(int u,int v,bool direction){
	link[++edge_counter]=adjacency[u];adjacency[u]=edge_counter;
	destination[edge_counter]=v;edge_direction[edge_counter]=direction;
}
int power_mod(int base,int exp=PRIME-2){
	int result=1;
	while(exp){
		if(exp&1) result=1ll*result*base%PRIME;
		base=1ll*base*base%PRIME;
		exp>>=1;
	}
	return result;
}
void compute_dp(int u,int parent){
	subtree_size[u]=3;
	memo[u][1]=1ll*prob[u][1]*prob[u][0]%PRIME;
	memo[u][2]=2ll*prob[u][2]*prob[u][0]%PRIME;
	memo[u][3]=3ll*prob[u][3]*prob[u][0]%PRIME;
	for(int i=adjacency[u];i;i=link[i]){
		int v=destination[i];
		if(v==parent) continue;
		compute_dp(v,u);
		for(int j=1;j<=subtree_size[u];++j) buffer[j]=memo[u][j],memo[u][j]=0;
		for(int j=1;j<=subtree_size[u];++j)
			for(int k=1;k<=subtree_size[v];++k){
				int tmp=1ll*buffer[j]*memo[v][k]%PRIME;
				if(edge_direction[i]) memo[u][j+k]=(memo[u][j+k]+tmp)%PRIME;
				else memo[u][j+k]=(memo[u][j+k]+PRIME-tmp)%PRIME,memo[u][j]=(memo[u][j]+tmp)%PRIME;
			}
		subtree_size[u]+=subtree_size[v];
	}
	for(int i=1;i<=subtree_size[u];++i) memo[u][i]=1ll*memo[u][i]*modular_inverse[i]%PRIME;
}
int main(){
	total_nodes=read();modular_inverse[1]=1;result=0;
	for(int i=2;i<=3*total_nodes;++i) modular_inverse[i]=1ll*modular_inverse[PRIME%i]*(PRIME-PRIME/i)%PRIME;
	for(int i=1;i<=total_nodes;++i){
		prob[i][1]=read();
		prob[i][2]=read();
		prob[i][3]=read();
		prob[i][0]=power_mod(prob[i][1]+prob[i][2]+prob[i][3]);
	}
	for(int i=1;i<total_nodes;++i){
		int u=read(),v=read();
		add_link(u,v,1);add_link(v,u,0);
	}
	compute_dp(1,0);
	for(int i=1;i<=3*total_nodes;++i) result=(result+memo[1][i])%PRIME;
	printf("%d\n",result);
	return 0;
}

Probabilistic computations often exhibit counterintuitive behavior. When dealing with problems where connected component solutions are easily computable but edge removal configurations are exponentially numerous ((O(2^n))), maintaining inclusion-exclusion coefficients within DP processes prvoides an effective optimization strategy.