2023 CCPC 华为云计算挑战赛 hdu7401 流量监控(树形dp)

题目

流量监控 - 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的决策，

u的决策实际有三种， 要么是(，要么是)，要么从树上抠掉

代码

#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;
}