Nowcodercontest5278G血压游戏
做法非常多。。。
比如对于同一层的点直接建立虚树,然后模拟dp即可
如果不想建虚树,可以直接维护合并,每次合并得到的\(\text{LCA}\)一定是同层点按照dfs序排序之后相邻两点的\(\text{LCA}\)之一
处理出所有这样的LCA,然后按照dep从大到小依次操作
用一个set维护,每次取出子树区间里的点合并上来即可。。。
不知道\(O(n)\)怎么写
const int N=2e5+10;
int n,rt;
int a[N];
vector <int> G[N];
vector <pair <int,int> > E[N];
int fa[N][20],L[N],R[N],dfn,id[N],dep[N];
void dfs(int u,int f) {
dep[u]=dep[fa[u][0]=f]+1;
id[L[u]=++dfn]=u;
rep(i,1,19) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:G[u]) if(v!=f) dfs(v,u);
R[u]=dfn;
}
int LCA(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
for(int del=dep[x]-dep[y],i=0;(1<<i)<=del;++i) if(del&(1<<i)) x=fa[x][i];
if(x==y) return x;
drep(i,19,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
ll ans;
int line[N];
set <pair <int,ll> > st;
void Solve(int d) {
sort(E[d].begin(),E[d].end()); //按照dfs排序之后取相邻的LCA
int n=E[d].size();
int cnt=0;
rep(i,1,n-1) line[++cnt]=LCA(id[E[d][i-1].first],id[E[d][i].first]);
line[++cnt]=rt;
sort(line+1,line+cnt+1,[&](int x,int y){ return (dep[x]>dep[y])||(dep[x]==dep[y] && x<y); }),cnt=unique(line+1,line+cnt+1)-line-1;
st.clear();
rep(i,0,n-1) st.insert(E[d][i]);
rep(i,1,cnt) {
int l=L[line[i]],r=R[line[i]];
ll s=0;
for(auto it=st.lower_bound(make_pair(l,0));it!=st.end();) {// set暴力维护合并
if(it->first>r) break;
s+=max(1ll,it->second-(dep[id[it->first]]-dep[line[i]]));
auto tmp=it; ++it;
st.erase(tmp);
}
st.insert(make_pair(L[line[i]],s));
}
ll t=st.begin()->second;
ans+=max(1ll,t-1);
}
int main(){
n=rd(),rt=rd();
rep(i,1,n) a[i]=rd();
rep(i,2,n) {
int u=rd(),v=rd();
G[u].pb(v),G[v].pb(u);
}
dfs(rt,0);
rep(i,1,n) if(a[i]) E[dep[i]].pb(make_pair(L[i],a[i]));
rep(i,1,n) if(E[i].size()) Solve(i);
printf("%lld\n",ans);
}