CodeForces-1118 F 1 Tree Cutting(Easy Version)(ツリーdp/dfs+思考)
Tree Cutting (Easy Version)
1つの木があって、各ノードは3种类の色があって、赤と青あるいは无色で、どのように分割して木を半分に分けることができて、しかも赤と青はそれぞれ2つの侧に位置します.
まず、赤と青のノードが全部で何個あるかを記録し、dfsを走って各ノードのサブツリー上の赤と青のノードの数を記録し、最後に、赤のノード=x青=0、または赤=0青=y、ans++でCodeを遍歴します.
1つの木があって、各ノードは3种类の色があって、赤と青あるいは无色で、どのように分割して木を半分に分けることができて、しかも赤と青はそれぞれ2つの侧に位置します.
まず、赤と青のノードが全部で何個あるかを記録し、dfsを走って各ノードのサブツリー上の赤と青のノードの数を記録し、最後に、赤のノード=x青=0、または赤=0青=y、ans++でCodeを遍歴します.
#include
#include
#include
#include
#include
#include
#include
#define inf 9654234
#define ll long long
using namespace std;
const int maxn=300007;
vector<int> ve[maxn];
int a[maxn],red[maxn],bule[maxn],x=0,y=0,ans=0;
void dfs(int u,int fa){
if(a[u]==1) red[u]=1;
if(a[u]==2) bule[u]=1;
for(auto v:ve[u]){
if(v==fa) continue;
dfs(v,u);
red[u]+=red[v];
bule[u]+=bule[v];
}
}
void solve(int u,int fa){
for(auto v:ve[u]){
if(v==fa) continue;
solve(v,u);
if(red[v]==x&&bule[v]==0||red[v]==0&&bule[v]==y) ans++;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
if(a[i]==1) x++;
if(a[i]==2) y++;
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
ve[u].push_back(v);
ve[v].push_back(u);
}
dfs(1,0);
solve(1,0);
// cout<
cout<<ans<<"
";
return 0;
}