题目
流量监控 - HDU 7401 - Virtual Judge
简单来说，T(T<=20)组样例，sumn不超过2e4
每次给定一棵n(n<=2000)个点的树，两问：
①将n个点恰拆成n/2个pair(u,v)，要求一个点是另一个点的祖先，求方案数
②若两个pair(u,v)、(w,x)满足：
u是v、w、x的祖先，w是v、x的祖先，v是x的祖先
即，四个点都在x通往根的路径上，且[u,v]和[w,x]相交，则称形成了一个区间交，
在①的所有合法方案数中，求区间交的总数
输出①、②的值，答案对998244353取模
思路来源
jiangly代码&heltion&tiger2005&夏老师
题解
对着jiangly代码，找了若干人讨论，终于讨论明白了
第一问，dp[i][j]表示i子树内当前有j个未匹配的点的方案数，
转移是一个树上背包，对子树做完树上背包之后，
再考虑u这个点的决策，要么是(，要么是)
换句话说，要么选一个之前未匹配的点进行匹配，要么新增一个未匹配的点
第二问，长度为4的祖先链（都在通往祖先的一条路径上），所以可以考虑把0-4都维护上，
这里实际是考虑每个长度为4的链的贡献，
即在dp的时候并不指定这四个点连的方式，只统计四元组的总方案数，
然后根据题目要求， 最后的时候将13相连、24相连
这相当于求从树上抠掉四个点（四个点在一条祖先链上）时，剩下的点构成合法方案的方案数
f[i][j][k]表示考虑到j的子树，当前抠掉了i个点，还有k个点没有匹配的方案数
相当于一个二维背包，i是一维，k是一维
转移先对u的子树v1、v2、...做背包，做k这一维的背包，
又因为不同子树之间的点并不在一条祖先链上，
所以i这一维做背包两两合并的时候，两棵子树的i这一维不能同时大于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);
}
}
}
}将子树都合并进来之后，再考虑u的决策，文章来源：https://www.toymoban.com/news/detail-662269.html
u的决策实际有三种， 要么是(，要么是)，要么从树上抠掉文章来源地址https://www.toymoban.com/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;
}到了这里，关于2023 CCPC 华为云计算挑战赛 hdu7401 流量监控(树形dp)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
