題目鏈接

單獨考慮每一種顏色，答案就是對于每種顏色至少經(jīng)過一次這種的路徑條數(shù)之和。反過來思考只需要求有多少條路徑?jīng)]有經(jīng)過這種顏色即可。

具體實現(xiàn)過程比較復雜，很神奇的一個樹形dp，下面給出一個含較詳細注釋的代碼及對應的一組自造的數(shù)據(jù)以及圖片來進行解釋

歡迎交流，給出意見~~~

數(shù)據(jù)

/*
第二行的1 2 3在圖中分別用紅黃藍來表示
15 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 */

?

含注釋的代碼

#include<bits/stdc++.h> using namespace std; typedef long long LL;const int N=2e5+5; int n; int c[N]; //各結(jié)點的顏色 int size[N]; //size[i]記錄結(jié)點i的子樹的大小，葉子為1 int vis[N]; //vis[i]記錄顏色i是否出現(xiàn)過 int sum[N]; //見函數(shù)內(nèi)注釋及圖片 vector<int> adj[N]; LL ans,de;LL C(LL a,LL b) //計算組合數(shù)，這樣寫是為了增加后面的代碼的可讀性 {LL ret=1;for(int i=1;i<=b;i++)ret=ret*(a+1-i)/i;return ret; }void dfs(int u,int pre) {// 定義 u 為“當前結(jié)點” // sum[c[u]]表示， 整棵樹中，已經(jīng)被dfs過的， // 與當前結(jié)點具有相同顏色的結(jié)點的所有子樹的大小之和// 不重復計數(shù)// 圖一展示了的是剛剛進入dfs(7,3)時sum[c[u]]包含的結(jié)點 printf("\n\n==================================\nEnter->%d\n\n",u);int all=0;size[u]=1;for(int to:adj[u]){if(to==pre) continue;int sumu_bd=sum[c[u]]; //bd : before dfs//記錄此次dfs前的sum[c[u]] dfs(to,u);size[u]+=size[to];int part=sum[c[u]]-sumu_bd; //dfs過后，sum[c[u]]會產(chǎn)生一個增量，用part來記錄這個增量 all+=part; //all用來記錄，對u dfs的過程中，sum[c[u]]產(chǎn)生的總增量//這是在為 u返回pre時更新sum[c[u]]做準備 printf("from %d return to %d\n",to,u);printf("all=%d,sumu_bd=%d,part=%d,sum[c[u]]=%d\n",all,sumu_bd,part,sum[c[u]]); printf("to=%d,size[to]=%d\n",to,size[to]);de+=C(size[to]-part,2); //size[to]-part的含義: 在to為根節(jié)點的子樹中，有一部分結(jié)點與to位于同一“塊”，// 這個塊以 與u顏色相同的結(jié)點（不含），或是葉子（含，若葉子與u顏色相同則不含） 為邊界// size[to]-part表示的是這個塊的大小// 圖二展示了 dfs(1,0)內(nèi)，剛剛執(zhí)行完dfs(2,1)后，更新de時的size[2]-part printf("\nnow,de=%d\n\n",de);}printf("\n\n=== leaving... ===\n\n");printf("pre_sum[c[u]]=%d\n",sum[c[u]]);sum[c[u]]+=size[u]-all;printf("after_sum[c[u]]=%d\n",sum[c[u]]);printf("\nleave from %d\n\n==================================\n\n",u); }int main() {int kase=0;while(~scanf("%d",&n)){memset(vis,0,sizeof(vis));memset(size,0,sizeof(size));memset(sum,0,sizeof(sum));for(int i=0;i<=n;i++) adj[i].clear();int c_num=0;de=0;for(int i=1;i<=n;i++){scanf("%d",&c[i]);if(!vis[c[i]]) c_num++;vis[c[i]]=1;}for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);adj[u].push_back(v);adj[v].push_back(u);}dfs(1,0);for(int i=1;i<=n;i++)if(i!=c[1]&&vis[i]) de+=C(n-sum[i],2);ans=C(n,2)*c_num-de;printf("Case #%d: %lld\n",++kase,ans);} }

圖一：

圖二：

?

AC代碼

#include<bits/stdc++.h> using namespace std; typedef long long LL;const int N=2e5+5; int n; int c[N]; int size[N]; int vis[N]; int sum[N]; vector<int> adj[N]; LL ans,de;LL C(LL a,LL b) {LL ret=1;for(int i=1;i<=b;i++)ret=ret*(a+1-i)/i;return ret; }void dfs(int u,int pre) {int all=0;size[u]=1;for(int to:adj[u]){if(to==pre) continue;int sumu_bd=sum[c[u]];dfs(to,u);size[u]+=size[to];int part=sum[c[u]]-sumu_bd;all+=part;de+=C(size[to]-part,2);}sum[c[u]]+=size[u]-all; }int main() {int kase=0;while(~scanf("%d",&n)){memset(vis,0,sizeof(vis));memset(size,0,sizeof(size));memset(sum,0,sizeof(sum));for(int i=0;i<=n;i++) adj[i].clear();int c_num=0;de=0;for(int i=1;i<=n;i++){scanf("%d",&c[i]);if(!vis[c[i]]) c_num++;vis[c[i]]=1;}for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);adj[u].push_back(v);adj[v].push_back(u);}dfs(1,0);for(int i=1;i<=n;i++)if(i!=c[1]&&vis[i]) de+=C(n-sum[i],2);ans=C(n,2)*c_num-de;printf("Case #%d: %lld\n",++kase,ans);} } 簡版的

?

轉(zhuǎn)載于:https://www.cnblogs.com/Just--Do--It/p/7239484.html

總結(jié)

以上是生活随笔為你收集整理的hdu 6035:Colorful Tree (2017 多校第一场 1003） 【树形dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。