제출 #465453

#제출 시각아이디문제언어결과실행 시간메모리
465453ohasanovPower Plant (JOI20_power)C++17
100 / 100
184 ms28872 KiB
#include<bits/stdc++.h>
using namespace std;

const int N = 200000 + 5;
vector <int> g[N];
int prelist[N], n;
string a;

int dfs(int node, int father)
{
    int st = a[node-1] - '0', best_child = 0, best = 0;
    for (int i = 0; i < (int)g[node].size(); i++)
    {
		int x = g[node][i];
        if (x != father){
			best = max(best, dfs(x, node));
			prelist[node] += prelist[x];
			best_child = max(best_child, prelist[x]);
		}
    }
    prelist[node] = max(st, prelist[node] - st);
    return max(best, max(prelist[node], best_child + st));
}

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cin >> a;
    cout << dfs(1, 0);
	
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...