結果
問題 | No.1215 都市消滅ビーム |
ユーザー |
|
提出日時 | 2020-08-30 08:40:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,449 ms / 6,000 ms |
コード長 | 3,390 bytes |
コンパイル時間 | 4,167 ms |
コンパイル使用メモリ | 190,060 KB |
実行使用メモリ | 27,636 KB |
最終ジャッジ日時 | 2024-11-15 06:16:56 |
合計ジャッジ時間 | 29,251 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
#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,rightint b[200000];ll calc1(ll t){//score onlyll ans=0;BIT<int>bit(K);vector<P>query;ll S=0;rep(i,K-2){int dep=lca.d1[lca.lca(L[i],c[K-1])];S+=d[i];query.push_back(P(t-dep-S,b[i]));}S=0;rep(i,K-1){S+=d[i];if(S+lca.d1[L[i]]<=t)ans++;}sort(query.begin(),query.end());vector<P>sum;ll s=0;for(int i=K-1;i>=0;i--){s+=d[i];sum.push_back(P(s,i));}sort(sum.begin(),sum.end());int g=0;for(auto p:query){while(g<sum.size()&&sum[g].first<=p.first){bit.add(sum[g].second,1);g++;}ans+=bit.sum2(p.second-1);}return ans;}struct st{ll a,b,c;};ll calc2(ll t){//score+depthll ans=0;BIT<int>bit(K);vector<st>query;query.push_back({t,0,K});ll S=0;rep(i,K-2){S+=d[i];query.push_back({t-S,i+2,b[i]});}sort(query.begin(),query.end(),[](st a,st b){return a.a<b.a;});vector<P>sum;ll s=0;for(int i=K-1;i>=0;i--){s+=d[i];sum.push_back(P(s+lca.d1[R[i]],i));}sort(sum.begin(),sum.end());int g=0;for(auto p:query){while(g<sum.size()&&sum[g].first<=p.a){bit.add(sum[g].second,1);g++;}ans+=bit.sum(p.c-1)-bit.sum(p.b-1);}return ans;}ll C(ll t){ll cnt=0;cnt+=calc1(t);cnt+=calc2(t);return cnt;}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];else R[i]=lca.lca(R[i+1],c[i]);}rep(i,K){if(i==0)L[i]=c[i];else L[i]=lca.lca(L[i-1],c[i]);}rep(i,K-2){int ok=K-1,ng=i+1;int node=lca.lca(c[K-1],L[i]);while(ok-ng>1){int t=(ok+ng)/2;if(lca.lca(L[i],R[t])==node)ok=t;else ng=t;}b[i]=ok;}ll E=K*(ll)(K+1)/2+1;E=(E+1)/2-1;ll ok=2e14,ng=-2e14;while(ok-ng>1){ll t=(ok+ng)/2;if(C(t)>=E)ok=t;else ng=t;}cout<<ok<<endl;}