제출 #293428

#제출 시각아이디문제언어결과실행 시간메모리
293428rama_pangPower Plant (JOI20_power)C++14
100 / 100
220 ms26196 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int N;
string S;
vector<int> adj[MAXN];

int ans = 0;
int dp[MAXN];

void Dfs(int u, int p) {
  int max_subtree = 0;
  int sum_subtree = 0;
  for (auto v : adj[u]) if (v != p) {
    Dfs(v, u);
    max_subtree = max(max_subtree, dp[v]);
    sum_subtree += dp[v];
  }
  max_subtree += (S[u] - '0');
  sum_subtree -= (S[u] - '0');
  sum_subtree = max(sum_subtree, (S[u] - '0'));
  ans = max({ans, max_subtree, sum_subtree});
  dp[u] = max(max_subtree - 2 * (S[u] - '0'), sum_subtree);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N;
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  cin >> S;
  Dfs(0, -1);
  cout << ans << "\n";
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...