제출 #1337504

#제출 시각아이디문제언어결과실행 시간메모리
1337504repmannMonochrome Points (JOI20_monochrome)C++20
0 / 100
1 ms348 KiB
#include <bits/stdc++.h>
using namespace std;
int N, sol = 1;
string S;
bitset <200001> B;
int DP[200001];
vector <int> VG[200001];
void DFS(int node, int parent = 0)
{
  int dp = 0, cnt = 0;
  for(int x : VG[node])
  {
    if(x == parent) continue;
    DFS(x, node);
    dp += DP[x];
    cnt += bool(DP[x]);
    DP[node] = max(DP[x], DP[node]);
  }
  DP[node] = max(dp, DP[node]);
  if(cnt > 1) sol = max(DP[node] - B[node], sol);
  else sol = max(DP[node] + B[node], sol);
  DP[node] = max(DP[node] - B[node], (int)B[node]);
//  cout << node << ": " << B[node] << ' ' << DP[node] << ' ' << dp << ' ' << cnt << '\n';
  return;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N;
  int u, v;
  for(int i = 1; i < N; i++)
  {
    cin >> u >> v;
    VG[u].push_back(v);
    VG[v].push_back(u);
  }
  cin >> S;
  for(int i = 1; i <= N; i++) B[i] = S[i - 1] == '1';
  for(int i = 1; i <= N; i++) DFS(i);
  cout << sol << '\n';
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...