Nowcodercontest5278G血压游戏

做法非常多。。。

比如对于同一层的点直接建立虚树，然后模拟dp即可

如果不想建虚树，可以直接维护合并，每次合并得到的一定是同层点按照dfs序排序之后相邻两点的之一

处理出所有这样的LCA，然后按照dep从大到小依次操作

用一个set维护，每次取出子树区间里的点合并上来即可。。。

不知道怎么写

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);
}