Submission #911530

#	Time	Username	Problem	Language	Result	Execution time	Memory
911530		MilosMilutinovic	Chase (CEOI17_chase)	C++14	0 / 100	4021 ms	14424 KiB

chase

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,l,tot;
int a[100005],v[200005],nxt[200005],h[100005],f[100005][20],dep[100005];
ll s[100005];

void addedge(int x,int y){
	v[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
	v[++tot]=x; nxt[tot]=h[y]; h[y]=tot;
}

void dfs1(int x,int px){
	dep[x]=dep[px]+1;
	f[x][0]=px;
	for(int i=1;i<20;i++) f[x][i]=f[f[x][i-1]][i-1];
	for(int p=h[x];p;p=nxt[p]){
		if(v[p]==px) continue;
		dfs1(v[p],x);
		s[x]+=a[v[p]];
	}
}

int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}

int dist(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}

int main(){
	n=readint(); l=readint();
	for(int i=1;i<=n;i++) a[i]=readint();
	for(int i=1;i<n;i++) addedge(readint(),readint());
	dfs1(1,0);
	ll ans=0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			if(dist(i,j)+1>l) continue;
			int k=lca(i,j);
			ll c=s[k]+a[k]+a[f[k][0]];
			int x=i;
			while(x!=k) c+=s[x],x=f[x][0];
			x=j;
			while(x!=k) c+=s[x],x=f[x][0];
			c-=min(a[i],a[j]);
			ans=max(ans,c);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

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