題目鏈接：點擊查看

題目大意：給定n個點，每個點的權(quán)值分別對應(yīng)顏色：0：無顏色，1：紅色，2：藍色，現(xiàn)在需要切割邊，使切割后的兩個部分不能出現(xiàn)紅色和藍色摻雜的部分，也就是說兩個部分必須只能各自含有一個顏色，問這樣的邊最多能有幾條

題目分析：樹形dp的思想，用dfs記錄以當(dāng)前點為根節(jié)點的子樹中紅色點和藍色點的個數(shù)，邊界為當(dāng)該子樹中紅色節(jié)點或藍色節(jié)點等于整棵樹中的紅色節(jié)點或藍色節(jié)點，并且另一種顏色的節(jié)點數(shù)量為0時，表示該子樹只包含有一種全部顏色的節(jié)點，故當(dāng)前邊是符合條件的，記錄后輸出即可

上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=3e5+100;int a[N];int blue[N],red[N];vector<int>node[N];int ans;void dfs(int u,int fa) {if(a[u]==1)red[u]=1;if(a[u]==2)blue[u]=1;for(int i=0;i<node[u].size();i++){int v=node[u][i];if(fa==v)continue;dfs(v,u);blue[u]+=blue[v];red[u]+=red[v];}if(blue[u]==blue[0]&&red[u]==0||red[u]==red[0]&&blue[u]==0)//記錄符合條件的邊數(shù)ans++; }int main() { // freopen("input.txt","r",stdin);int n;while(scanf("%d",&n)!=EOF){memset(blue,0,sizeof(blue));memset(red,0,sizeof(red));for(int i=1;i<=n;i++){node[i].clear();scanf("%d",a+i);if(a[i]==1)red[0]++;if(a[i]==2)blue[0]++;}for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}ans=0;dfs(1,-1);cout<<ans<<endl;} return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1118F1 Tree Cutting (Easy Version)(树形dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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