# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
881067 | VerdantGMD | Power Plant (JOI20_power) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>#include <vector>using namespace std;vector<int> tab[200005];int zp[200005];int dp[200005];bool val[200005];int maxwyn = 0;void dfs(int p, int parent){ int sum = 0; int maxx = 0; for(int i = 0; i < tab[p].size(); i++) { if(tab[p][i] != parent) { dfs(tab[p][i], p); } } for(int i = 0; i < tab[p].size(); i++) { if(tab[p][i] != parent) { sum += zp[tab[p][i]]; maxx = max(maxx, zp[tab[p][i]]); } } if(val[p] == true) { zp[p] = max(1, sum - 1); dp[p] = maxx + 1; } else { zp[p] = sum; dp[p] = maxx; } maxwyn = max(zp[p], maxwyn); maxwyn = max(dp[p], maxwyn);}int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; tab[a].push_back(b); tab[b].push_back(a); } string a; cin >> a; for(int i = 0; i < a.size(); i++) { val[i+1] = a[i] - '0'; } dfs(1, 0); /*for(int i = 1; i <= n; i++) { cout << i << " " << dp[i] << endl; }*/ cout << maxwyn;}