【題目描述】

【思路】
看了大佬的題解才想明白的，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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。