Submission #292883

#	Time	Username	Problem	Language	Result	Execution time	Memory
292883		limabeans	Power Plant (JOI20_power)	C++17	0 / 100	16 ms	23808 KiB

power

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



int n;
vector<int> g[maxn];
string s;

int best=0;

int dfs(int at, int p) {
    vector<int> ch;
    for (int to: g[at]) {
	if (to==p) continue;
	int rec=dfs(to,at);
	if (rec>0) {
	    ch.push_back(rec);
	}
    }
    int res=int(s[at]-'0'); // self
    
    if (!ch.empty()) {
	sort(ch.begin(), ch.end());

	// self + best child
	if (s[at]=='1') {
	    best=max(best,1+ch.back());
	}

	// join children thru us
	int sum = std::accumulate(ch.begin(), ch.end(), 0);
	res = max(res, sum - int(s[at]-'0'));
    }

    cout<<at+1<<": "<<res<<endl;
    cout<<"ch: ";
    for (int c: ch) cout<<c<<" ";
    cout<<endl;
				     
    
    best=max(best,res);
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	--u; --v;
	g[u].push_back(v);
	g[v].push_back(u);
    }
    
    cin>>s;
    dfs(0,-1);
    // for (int i=0; i<n; i++) {
    // 	dfs(i,-1);	
    // }
    cout<<best<<endl; 
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53