제출 #1175041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175041		Dan4Life	Chase (CEOI17_chase)	C++20	0 / 100	142 ms	11420 KiB

chase

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
const int mxN = (int)1e5+10;
const ll LINF = (ll)1e18;
ll n, v, cen, ans;
bitset<mxN> vis;
vi adj[mxN];
ll a[mxN], b[mxN], sub[mxN];

template<class T, int SZ>
struct Fenwick{
	T fen[SZ];
	void init(){
		for(int i = 0; i < SZ; i++) fen[i]=-LINF;
	}
	void upd(int x, T v){
		for(++x; x<SZ; x+=x&-x) fen[x]=max(fen[x],v);
	}
	T query(int x){
		T s = -LINF;
		for(++x; x>0; x-=x&-x) s=max(s,fen[x]);
		return s;
	}
};
Fenwick<ll, 105> fen;

int dfsSz(int s, int p){
	sub[s] = 1;
	for(auto u : adj[s]){
		if(u==p or vis[u]) continue;
		sub[s]+=dfsSz(u,s);
	}
	return sub[s];
}

int fcen(int s, int p, int n){
	for(auto u : adj[s]){
		if(u==p or vis[u]) continue;
		if(sub[u]>n/2) return fcen(u,s,n);
	}
	return s;
}

void dfs(int s, int p, int dep, ll sum, int ok){
	if(dep>v) return;
	if(ok==0) fen.upd(dep,sum+a[s]);
	else if(ok==1) ans=max(ans, sum+b[cen]+fen.query(v-dep-1));
	else if(dep<v) ans=max(ans, max(a[cen],a[s])+sum);
	for(auto u : adj[s]){
		if(u==p or vis[u]) continue;
		dfs(u,s,dep+1,sum+b[u],ok);
	}
}

void cen_dec(int s, int p){
	cen = fcen(s,p,dfsSz(s,p)); 
	vis[cen] = 1; fen.init();
	for(auto u : adj[cen]){
		if(u==p or vis[u]) continue;
		dfs(u,cen,1,b[u],1); dfs(u,cen,1,b[u],0);
	}
	dfs(cen,p,0,b[cen],2); fen.init();
	for(int j = sz(adj[cen])-1; j>=0; j--){
		int u = adj[cen][j]; if(u==p or vis[u]) continue;
		dfs(u,cen,1,b[u],1); dfs(u,cen,1,b[u],0);
	}
	for(auto u : adj[cen]){
		if(u==p or vis[u]) continue;
		cen_dec(u,cen);
	}
}

int main(){
	cin >> n >> v;
	for(int i = 1; i <= n; i++) cin >> a[i], b[i]=-a[i];
	for(int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	if(!v){cout<<0<<"\n"; return 0;}
	for(int i = 1; i <= n; i++)
		for(auto u : adj[i]) b[i]+=a[u];
	cen_dec(1,0); cout << ans << "\n";
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30