# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
881067 | VerdantGMD | Power Plant (JOI20_power) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;}