#include <bits/stdc++.h>
using namespace std;
void dfs(int ind,int pros,vector<vector<int>>& sta,vector<vector<int>>& dp,vector<bool>& plant,int& najv){
// cout << ind << "\n";
cout.flush();
for (int i=0;i<sta[ind].size();i++){
int ind2=sta[ind][i];
if (ind2==pros){
continue;
}
dfs(ind2,ind,sta,dp,plant,najv);
}
if (!plant[ind]){
int najv1=0;
int najv2=0;
for (int i=0;i<sta[ind].size();i++){
int ind2=sta[ind][i];
if (ind2==pros){
continue;
}
najv1+=dp[ind2][0];
najv2+=max(dp[ind2][0],dp[ind2][1]);
}
dp[ind][0]=najv1;
dp[ind][1]=najv2;
najv=max({najv,dp[ind][0],dp[ind][1]});
// cout << ind+1 << ": " << najv1 << " " << najv2 << "\n";
}
else {
int najv1=0;
int najv2=0;
int najv3=0;
for (int i=0;i<sta[ind].size();i++){
int ind2=sta[ind][i];
if (ind2==pros){
continue;
}
najv1+=dp[ind2][0];
najv2+=max(dp[ind2][0],dp[ind2][1]);
}
najv3=najv1;
for (int i=0;i<sta[ind].size();i++){
int ind2=sta[ind][i];
if (ind2==pros){
continue;
}
najv3=max(najv3,najv1-dp[ind2][0]+dp[ind2][1]);
}
dp[ind][0]=najv1;
dp[ind][1]=max(najv1+1,najv2-1);
najv=max({najv,dp[ind][0],dp[ind][1],najv3+1});
// cout << ind+1 << ": " << najv1 << " " << max(najv1+1,max(najv2-1,najv3+1)) << "\n";
}
}
// 0 -> ti 0, oko tebe svi 0
// 1 -> ti 0, oko tebe jedan 1
// 2 -> ti 0, oko tebe svejedno
// 3 -> ti 1, oko tebe svi 0
// 4 -> ti 1, oko tebe jedan 1
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#define task "task"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".ans", "w", stdout);
}
int n;
cin >> n;
vector<vector<int>> sta(n,vector<int>{});
for (int i=0;i<n-1;i++){
// cout << "a" << endl;
int unos;
int unos2;
cin >> unos >> unos2;
sta[--unos].push_back(--unos2);
sta[unos2].push_back(unos);
// cout << "b" << endl;
}
string s;
cin >> s;
vector<bool> plant(n,0);
for (int i=0;i<n;i++){
if (s[i]=='1'){
plant[i]=1;
}
}
int najv=0;
vector<vector<int>> dp(n,vector<int>(2,0));
dfs(0,0,sta,dp,plant,najv);
cout << najv << "\n";
}
컴파일 시 표준 에러 (stderr) 메시지
power.cpp: In function 'int main()':
power.cpp:78:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:79:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | freopen(task".ans", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |