題目

流量監(jiān)控 - HDU 7401 - Virtual Judge

簡單來說，T(T<=20)組樣例，sumn不超過2e4

每次給定一棵n(n<=2000)個(gè)點(diǎn)的樹，兩問：

①將n個(gè)點(diǎn)恰拆成n/2個(gè)pair(u,v)，要求一個(gè)點(diǎn)是另一個(gè)點(diǎn)的祖先，求方案數(shù)

②若兩個(gè)pair(u,v)、(w,x)滿足：

u是v、w、x的祖先，w是v、x的祖先，v是x的祖先

即，四個(gè)點(diǎn)都在x通往根的路徑上，且[u,v]和[w,x]相交，則稱形成了一個(gè)區(qū)間交，

在①的所有合法方案數(shù)中，求區(qū)間交的總數(shù)

輸出①、②的值，答案對998244353取模

思路來源

jiangly代碼&heltion&tiger2005&夏老師

題解

?對著jiangly代碼，找了若干人討論，終于討論明白了

第一問，dp[i][j]表示i子樹內(nèi)當(dāng)前有j個(gè)未匹配的點(diǎn)的方案數(shù)，

轉(zhuǎn)移是一個(gè)樹上背包，對子樹做完樹上背包之后，

再考慮u這個(gè)點(diǎn)的決策，要么是(，要么是)

換句話說，要么選一個(gè)之前未匹配的點(diǎn)進(jìn)行匹配，要么新增一個(gè)未匹配的點(diǎn)

第二問，長度為4的祖先鏈（都在通往祖先的一條路徑上），所以可以考慮把0-4都維護(hù)上，

這里實(shí)際是考慮每個(gè)長度為4的鏈的貢獻(xiàn)，

即在dp的時(shí)候并不指定這四個(gè)點(diǎn)連的方式，只統(tǒng)計(jì)四元組的總方案數(shù)，

然后根據(jù)題目要求， 最后的時(shí)候?qū)?3相連、24相連

這相當(dāng)于求從樹上摳掉四個(gè)點(diǎn)（四個(gè)點(diǎn)在一條祖先鏈上）時(shí)，剩下的點(diǎn)構(gòu)成合法方案的方案數(shù)

f[i][j][k]表示考慮到j(luò)的子樹，當(dāng)前摳掉了i個(gè)點(diǎn)，還有k個(gè)點(diǎn)沒有匹配的方案數(shù)

相當(dāng)于一個(gè)二維背包，i是一維，k是一維

轉(zhuǎn)移先對u的子樹v1、v2、...做背包，做k這一維的背包，

又因?yàn)椴煌訕渲g的點(diǎn)并不在一條祖先鏈上，

所以i這一維做背包兩兩合并的時(shí)候，兩棵子樹的i這一維不能同時(shí)大于0

        rep(a,0,4){
			rep(b,0,4){
				if(a && b)continue;
				rep(i,0,sz[u]){
					rep(j,0,sz[v]){
						add(tmp[a+b][i+j],1ll*f[a][u][i]*f[b][v][j]%mod);
					}
				}
			}
		}

將子樹都合并進(jìn)來之后，再考慮u的決策，

u的決策實(shí)際有三種， 要么是(，要么是)，要么從樹上摳掉文章來源地址http://www.zghlxwxcb.cn/news/detail-662269.html

代碼

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e3+10,mod=998244353,inv2=(mod+1)/2;
int T,n,u,v,sz[N],tmp[5][N],f[5][N][N];
vector<int>e[N];
void add(int &x,int y){
	x=(x+y)%mod;
}
void dfs(int u,int fa){
	sz[u]=1;
	f[0][u][0]=1;
	for(auto &v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
		memset(tmp,0,sizeof tmp);
		rep(a,0,4){
			rep(b,0,4){
				if(a && b)continue;
				rep(i,0,sz[u]){
					rep(j,0,sz[v]){
						add(tmp[a+b][i+j],1ll*f[a][u][i]*f[b][v][j]%mod);
					}
				}
			}
		}
		sz[u]+=sz[v];
		rep(a,0,4){
			rep(i,0,sz[u]){
				f[a][u][i]=tmp[a][i];
			}
		}
	}
	memset(tmp,0,sizeof tmp);
	rep(a,0,4){
		rep(i,0,sz[u]){
			if(i)add(tmp[a][i-1],1ll*f[a][u][i]*i%mod);
			add(tmp[a][i+1],f[a][u][i]);
			if(a<4)add(tmp[a+1][i],f[a][u][i]);
		}
	}
	rep(a,0,4){
		rep(i,0,sz[u]){
			f[a][u][i]=tmp[a][i];
		}
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		sci(n);
		rep(i,1,n){
			e[i].clear();
			sz[i]=0;
		}
		memset(f,0,sizeof f);
		rep(i,2,n){
			sci(u),sci(v);
			e[u].pb(v);
			e[v].pb(u);
		}
		dfs(1,0);
		printf("%d %d\n",f[0][1][0],f[4][1][0]);
	}
	return 0;
}

到了這里，關(guān)于2023 CCPC 華為云計(jì)算挑戰(zhàn)賽 hdu7401 流量監(jiān)控(樹形dp)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！