Submission #1272456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272456		thuhienne	Power Plant (JOI20_power)	C++20	100 / 100	200 ms	26944 KiB

power

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

int n;
vector <int> adj[200009];
bool powerplant[200009];

int dp[200009],res[200009];
//dp i: max profit sau khi xet den cay con goc i va da tru di chi phi sua chua tu 1 thang dc chon
//bat ky cho den i. Tuc la ta tinh truoc chi phi khi gia su co 1 thang nao do ngoai cc goc i

void dfs(int node,int par) {
	for (auto x : adj[node]) if (x != par) dfs(x,node);
	//cal dp
	
	//TH1: k kich hoat node -> hop cua tat ca cac dp
	for (auto x : adj[node]) if (x != par) dp[node] += dp[x];
	dp[node] -= powerplant[node];
	//Th nay ta coi nhu co 2 thang powerplant o 2 nhanh khac nhau vi neu k thi cx cha toi uu bang
	
	//TH2: kich hoat node (neu co) -> k duoc chon thang khac do ta dang coi nhu tru khau hao
	dp[node] = max(dp[node],(int)powerplant[node]);
	
	//cal res
	
	//TH1: tap cac dinh duoc chon thuoc cay con goc child
	for (auto x : adj[node]) if (x != par) res[node] = max(res[node],res[x]);
	//TH2: hop cua cac dinh (so nhanh duoc chon >= 2)
	res[node] = max(res[node],dp[node]);
	//TH3: chon node va 1 nhanh nao do
	for (auto x : adj[node]) if (x != par) res[node] = max(res[node],dp[x] + powerplant[node]);
	
	
	
}

int main() {
//  ios_base::sync_with_stdio(0);
//  cin.tie(nullptr);
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);
	cin >> n;
	for (int i = 1;i < n;i++) {
		int u,v;cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1;i <= n;i++) {
		char c;cin >> c;
		powerplant[i] = c - '0';
	}
	dfs(1,-1);
	cout << *max_element(res + 1,res + 1 + n);
}

/*
  Thuong em khi mua thu
  Thuong em sang mua ha
  Thuong em bang qua mua dong,gui gio xuan om em vao long
  Thuong em bao mua mua
  Tham thuong luon bao mua nang
  Thuong yeu em khong doi thay,gio mat em tim toi hao gay ):
*/

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