結果

問題 No.1215 都市消滅ビーム
ユーザー autumn-eel
提出日時 2020-08-30 09:08:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,534 bytes
コンパイル時間 2,425 ms
コンパイル使用メモリ 183,204 KB
実行使用メモリ 814,968 KB
最終ジャッジ日時 2024-11-15 06:16:22
合計ジャッジ時間 100,564 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 1
other AC * 17 TLE * 1 MLE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;

class LCA{
public:
	vector<vector<int>>E;
	vector<vector<int>>par;
	vector<int>d1;
	int MAX_LOG=18;
	int n;
	LCA(){}
	LCA(int N){
		n=N;
		E=vector<vector<int>>(n);
		par=vector<vector<int>>(MAX_LOG,vector<int>(n));
		d1=vector<int>(n);
	}
	void add_edge(int a,int b){
		E[a].push_back(b);
		E[b].push_back(a);
	}
private:
	void dfs(int u,int p,int a){
		par[0][u]=p;d1[u]=a;
		for(auto&v:E[u]){
			if(v!=p)dfs(v,u,a+1);
		}
	}
	bool flag=false;
	void init(){
		dfs(0,-1,0);
		for(int i=1;i<MAX_LOG;i++)for(int j=0;j<n;j++){
			if(par[i-1][j]==-1)par[i][j]=-1;
			else par[i][j]=par[i-1][par[i-1][j]];
		}
		flag=true;
	}
public:
	int lca(int u,int v){
		if(!flag)init();
		if(d1[u]>d1[v])swap(u,v);
		for(int i=0;i<MAX_LOG;i++){
			if((d1[v]-d1[u])>>i&1)v=par[i][v];
		}
		if(u==v)return u;
		for(int i=MAX_LOG-1;i>=0;i--){
			if(par[i][u]!=par[i][v]){
				u=par[i][u];
				v=par[i][v];
			}
		}
		return par[0][u];
	}
};

template<class T>
class BIT{
public:
	vector<T>bit;
	T cnt;
	BIT(int n){
		bit=vector<T>(n+10);
		cnt=0;
	}
	void add(int k,T x){
		k++;
		while(k<(int)bit.size()){
			bit[k]+=x;
			k+=k&-k;
		}
		cnt+=x;
	}
	T sum(int k){
		k++;
		T res=0;
		while(k){
			res+=bit[k];
			k-=k&-k;
		}
		return res;
	}
	T sum2(int k){
		return cnt-sum(k);
	}
};

LCA lca;

int n,K;
int c[200000];
ll d[200000];

int L[200000],R[200000];//lca from left,right
int LR[200000]; // left+right end
int b[200000];
ll suml[200000],sumr[200000];

int main(){
	cin>>n>>K;
	lca=LCA(n);
	rep(i,K){
		scanf("%d",&c[i]);c[i]--;
	}
	rep(i,K)scanf("%lld",&d[i]);
	rep(i,n-1){
		int a,b;scanf("%d%d",&a,&b);a--;b--;
		lca.add_edge(a,b);
	}
	lca.lca(0,1);
	for(int i=K-1;i>=0;i--){
		if(i==K-1)R[i]=c[i],sumr[i]=d[i];
		else R[i]=lca.lca(R[i+1],c[i]),sumr[i]=sumr[i+1]+d[i];
	}
	rep(i,K){
		if(i==0)L[i]=c[i],suml[i]=d[i];
		else L[i]=lca.lca(L[i-1],c[i]),suml[i]=suml[i-1]+d[i];
	}
	vector<ll>V;
	V.push_back(L[K-1]+suml[K-1]);
	rep(i,K)for(int j=i+1;j<=K;j++){
		if(i==0){
			if(j==K)V.push_back(LLONG_MIN);
			else V.push_back(lca.d1[R[j]]+sumr[j]);
			continue;
		}
		if(j==K){
			V.push_back(lca.d1[L[i-1]]+suml[i-1]);
			continue;
		}
		V.push_back(lca.d1[lca.lca(L[i-1],R[j])]+suml[i-1]+sumr[j]);
	}
	sort(V.begin(),V.end());
	//~ for(auto p:V)cout<<p<<' ';
	//~ cout<<endl;
	ll E=K*(ll)(K+1)/2+1;
	E=(E+1)/2-1;
	cout<<V[E]<<endl;
}
/*
3 2
2 3
1 1
1 2
2 3
*/

/*
7 3
4 5 7
1 10 100
1 2
2 3
3 4
3 5
1 6
6 7
*/
0