51Nod 1322 - 关于树的函数（树DP）

【题目描述】

【思路】
看了大佬的题解才想明白的，f_zyj大佬的题解
两棵树，对第一棵树暴力枚举所有边，拆掉这条边后的两个子树对应两个集合 $A1,B1$，用 $dfs$ 枚举，然后在枚举出某一个 $A1,A2$ 时，所有在 $A1$ 中的节点 $u$，$used[u]=true$，现在对第二棵树枚举，$dfs2$ 枚举的时候和刚才 $dfs1$ 不同，这回是把节点 $u$ 和 $u$ 的所有子孙看成集合 $B1$，树上的其它节点看成是集合 $B2$，这样一来，可以递推的计算集合中元素的个数已经 $A1,B1$ 交集的大小，设第二棵树上节点 $u$ 对应的集合大小为 $num[u]$，和 $A1$ 的交集大小为 $dp[u]$，如果 $u$ 的所有儿子节点所在集合为 $S$ ，那么就有 num[u]=1+∑v∈Snum[v]num[u]=1+\sum_{v \in S}num[v]num[u]=1+v∈S∑​num[v] dp[u]={1+∑v∈Sdp[v]   (used[u]=true)       ∑v∈Sdp[v]   (used[u]=false) dp[u]=\begin{cases} 1+\sum_{v \in S}dp[v] \ \ \ (used[u]=true) \\ \ \ \ \ \ \ \ \sum_{v \in S}dp[v] \ \ \ (used[u]=false) \end{cases} dp[u]={1+∑v∈S​dp[v]   (used[u]=true)       ∑v∈S​dp[v]   (used[u]=false)​
而且只要知道 $A1,B1$ 的交集大小，并且 $A1，A2$交集为空，$B1,B2$交集为空，因此其余三对集合的交集大小也能推算出来，取一下最大值，不过题解里的“树归”是个啥？树上递归吗？不是很懂…

#include<bits/stdc++.h> #define max(a,b)(a>b?a:b) using namespace std; const int maxn=4005;struct Edge{int from,to;Edge(int f=0,int t=0):from(f),to(t){} };int n,a1; long long ans; bool used[maxn]; int num[maxn],dp[maxn]; vector<int> g1[maxn],g2[maxn]; Edge edges[maxn];void dfs1(int u,int fa){used[u]=true;++a1;for(int i=0;i<g1[u].size();++i){int v=g1[u][i];if(v!=fa && !used[v]) dfs1(v,u);} }void dfs2(int u,int fa){num[u]=1;dp[u]=used[u]?1:0;for(int i=0;i<g2[u].size();++i){int v=g2[u][i];if(v!=fa){dfs2(v,u);num[u]+=num[v];dp[u]+=dp[v];}}if(u!=0){//u=0时树没有被分成两部分所以不算 int b1=num[u];//集合a1和b1的交集大小为dp[u]int maxv=0;maxv=max(maxv,dp[u]);maxv=max(maxv,a1-dp[u]);maxv=max(maxv,b1-dp[u]);maxv=max(maxv,n-a1-b1+dp[u]);ans+=(long long)maxv*maxv;} }int main(){scanf("%d",&n);for(int i=0;i<n-1;++i){int u,v;scanf("%d%d",&u,&v);g1[u].push_back(v);g1[v].push_back(u);edges[i]=Edge(u,v);}for(int i=0;i<n-1;++i){int u,v;scanf("%d%d",&u,&v);g2[u].push_back(v);g2[v].push_back(u);}for(int i=0;i<n-1;++i){a1=0;memset(used,0,sizeof(used));dfs1(edges[i].from,edges[i].to);dfs2(0,-1);}printf("%lld\n",ans);return 0; }

转载于:https://www.cnblogs.com/wafish/p/10465115.html

总结

以上是生活随笔为你收集整理的51Nod 1322 - 关于树的函数（树DP）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。