题解：P12423 【MX-X12-T6】「ALFR Round 5」Coloring Nodes

· · 题解

首先，无解的情况比较显然，即询问的点为叶子且在 [l,r] 中，然而 [l,r] 并未包含所有叶子。

考虑根固定时怎么做：对于每个点 u，记录 f,l,r，分别表示 u 子树内叶子对应的区间是 [l_u,r_u]，u 到其子树内所有叶子路径上都有黑点的最小花费为 f_u，有转移：

f_u\gets\min\{w_u+h_u,g_u\}

其中 g_u=\sum\limits_{v\in\operatorname{son}_u} f_v，h_u=\sum\limits_{v\in\operatorname{subtree}_u\setminus\{u\}}[w_v\le 0]w_v。前者表示的是 u 染黑了的话，那么 u 子树内的叶子到根的路径上都有黑点了，所以它的子树内可以随便染黑；贪心地，染黑全部点权为非负数的点即可。后者表示 u 不染黑，让 u 的每个儿子自己染黑自己子树内的叶子即可。

对于 [l,r]，显然只有包含和无交两种情况。

现在来考虑怎么求答案。显然，一个点 u 如果对答案的贡献应为 f_u，并且如果 u 要产生贡献的话，那么它子树内的其它点一定不产生贡献，因此它要对答案贡献的充要条件应该是：L\le l_u\le r_u\le R\land(l_{fa_u}<L\lor r_{fa_u}>R)。

注意到如果 u 有贡献，那么它子树内的其它点都会对答案有贡献，考虑把一个点的贡献写成 f_u-g_u 的形式，容易发现，这样的话，对子树求和后的结果就正好为 f_u。

然后问题就转化为对于所有 L\le l_u\le r_u\le R 的 u 的 f_u-g_u 求和，二维数点即可，可以做到 O(nk\log n+q\log n)，其中 k 为查询的根数。

接下来考虑换根，容易发现在一次换根时，只有路径两端的点的 f,l,r,g,h 会发生变化，因此考虑在根固定的基础上，加上一维表示每个点作为根的时间戳 t_u，每次 f,l,r,g,h 变化时撤销旧的贡献并加入新的贡献，每次查询的要求就变成了 t\le t_{u_i},l_i\le l,r\le r_i，这是一个三维偏序。

实现的时候注意一下叶子需要特判，以及一些可能会导致 TLE 的常数因子，时间复杂度 O((n+q)\log^2(n+q))。

:::info[code]

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,q,m,rt,nowt,tim[N],tot,ans[N],t[N],u[N],l[N][2],r[N][2],_l[N],_r[N],posl[N],posr[N],f[N],g[N],_g[N],h[N],_h[N],w[N],fa[N],cnt[N],c[N];
bool leaf[N];
vector<int> G[N];
struct node{ int t,l,r,w,id; }p[N<<3],pp[N<<3];
bool cmp1(node a,node b){
    if(a.t==b.t){
        if(a.l==b.l){
            if(a.r==b.r) return a.id<b.id;
            return a.r<b.r;
        }
        return a.l>b.l;
    }
    return a.t<b.t;
}
bool cmp2(node a,node b){ return a.l>b.l; }
void dfs1(int u){
    if(leaf[u]){
        f[u]=w[u],g[u]=0;
        l[u][0]=r[u][0]=u,posl[u]=posr[u]=u;
    } else{
        for(auto v:G[u]){
            if(v==fa[u]) continue;
            fa[v]=u;
            dfs1(v);
            g[u]+=f[v];
            h[u]+=h[v];
            if(w[v]<=0) h[u]+=w[v];
            if(l[v][0]<l[u][0]) l[u][1]=l[u][0],l[u][0]=l[v][0],posl[u]=v;
            else l[u][1]=min(l[u][1],l[v][0]);
            if(r[v][0]>r[u][0]) r[u][1]=r[u][0],r[u][0]=r[v][0],posr[u]=v;
            else r[u][1]=max(r[u][1],r[v][0]);
        }
        f[u]=min(g[u],h[u]+w[u]);
    }
    if(f[u]-g[u]) p[++m]=node({tot,l[u][0],r[u][0],f[u]-g[u],0});
}
void dfs2(int u){
    if(f[u]-g[u]) p[++m]=node({tot,l[u][0],r[u][0],-(f[u]-g[u]),0});
    if(!leaf[u]){
        if(min(w[u]+h[u]+_h[u],g[u]+_g[u])-(g[u]+_g[u])){
            p[++m]=node({tot,min(l[u][0],_l[u]),max(r[u][0],_r[u]),min(w[u]+h[u]+_h[u],g[u]+_g[u])-(g[u]+_g[u]),0});
            p[++m]=node({tot+1,min(l[u][0],_l[u]),max(r[u][0],_r[u]),-(min(w[u]+h[u]+_h[u],g[u]+_g[u])-(g[u]+_g[u])),0});
        }
    } else{
        p[++m]=node({tot,min(l[u][0],_l[u]),max(r[u][0],_r[u]),w[u]+_h[u]-_g[u],0});
        p[++m]=node({tot+1,min(l[u][0],_l[u]),max(r[u][0],_r[u]),-(w[u]+_h[u]-_g[u]),0});
    }
    for(auto v:G[u]){
        if(v==fa[u]) continue;
        t[v]=++tot;
        _g[v]=min(w[u]+h[u]+_h[u]-h[v]-(w[v]<=0?w[v]:0),g[u]+_g[u]-f[v]);
        _h[v]=_h[u]+h[u]-h[v]-(w[v]<=0?w[v]:0)+(w[u]<=0?w[u]:0);
        if(posl[u]==v) _l[v]=min(l[u][1],_l[u]);
        else _l[v]=min(l[u][0],_l[u]);
        if(posr[u]==v) _r[v]=max(r[u][1],_r[u]);
        else _r[v]=max(r[u][0],_r[u]);
        if(g[v]-(g[u]+_g[u]-f[v])){
            if(posl[u]==v&&posr[u]==v) p[++m]=node({tot,min(l[u][1],_l[u]),max(r[u][1],_r[u]),_g[v]-(g[u]+_g[u]-f[v]),0});
            else if(posl[u]==v) p[++m]=node({tot,min(l[u][1],_l[u]),max(r[u][0],_r[u]),_g[v]-(g[u]+_g[u]-f[v]),0});
            else if(posr[u]==v) p[++m]=node({tot,min(l[u][0],_l[u]),max(r[u][1],_r[u]),_g[v]-(g[u]+_g[u]-f[v]),0});
            else p[++m]=node({tot,min(l[u][0],_l[u]),max(r[u][0],_r[u]),_g[v]-(g[u]+_g[u]-f[v]),0});
        }
        dfs2(v);
        if(g[v]-(g[u]+_g[u]-f[v])){
            if(posl[u]==v&&posr[u]==v) p[++m]=node({tot+1,min(l[u][1],_l[u]),max(r[u][1],_r[u]),-(_g[v]-(g[u]+_g[u]-f[v])),0});
            else if(posl[u]==v) p[++m]=node({tot+1,min(l[u][1],_l[u]),max(r[u][0],_r[u]),-(_g[v]-(g[u]+_g[u]-f[v])),0});
            else if(posr[u]==v) p[++m]=node({tot+1,min(l[u][0],_l[u]),max(r[u][1],_r[u]),-(_g[v]-(g[u]+_g[u]-f[v])),0});
            else p[++m]=node({tot+1,min(l[u][0],_l[u]),max(r[u][0],_r[u]),-(_g[v]-(g[u]+_g[u]-f[v])),0});
        }
    }
    if(f[u]-g[u]) p[++m]=node({tot+1,l[u][0],r[u][0],f[u]-g[u],0});
}
int lowbit(int x){ return x&-x; }
void add(int x,int y){
    for(;x<=n;x+=lowbit(x)){
        if(tim[x]!=nowt) c[x]=0,tim[x]=nowt;
        c[x]+=y;
    }
}
int ask(int x){
    int s=0;
    for(;x;x-=lowbit(x)) if(tim[x]==nowt) s+=c[x];
    return s;
}
void cdq(int l,int r){
    if(l==r) return;
    int mid=l+r>>1;
    cdq(l,mid),cdq(mid+1,r);
    ++nowt;
    int pos=l-1;
    for(int i=mid+1;i<=r;++i){
        while(pos+1<=mid&&p[pos+1].l>=p[i].l){
            ++pos;
            if(!p[pos].id) add(p[pos].r,p[pos].w);
        }
        if(p[i].id) ans[p[i].id]+=ask(p[i].r);
    }
    int tot=0,pl=l,pr=mid+1;
    while(pl<=mid||pr<=r)
        if(pr>r||(pl<=mid&&p[pl].l>=p[pr].l)) pp[++tot]=p[pl++];
        else pp[++tot]=p[pr++];
    for(int i=1;i<=tot;++i) p[l+i-1]=pp[i];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>w[i];
    for(int i=1,u,v;i<n;++i){
        cin>>u>>v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    if(n==1){
        while(q--) cout<<w[1]<<endl;
        return 0;
    }
    for(int i=1;i<=n;++i)
        if(G[i].size()==1) leaf[i]=true;
        else rt=i;
    for(int i=1;i<=n;++i) cnt[i]=cnt[i-1]+leaf[i];
    t[rt]=tot=1;
    memset(l,0x3f,sizeof(l)),memset(r,-0x3f,sizeof(r));
    dfs1(rt);
    memset(_l,0x3f,sizeof(_l)),memset(_r,-0x3f,sizeof(_r));
    dfs2(rt);
    for(int i=1,u,l,r;i<=q;++i){
        cin>>u>>l>>r;
        if(leaf[u]&&l<=u&&u<=r&&cnt[r]-cnt[l-1]!=cnt[n]){
            ans[i]=1e18;
            continue;
        }
        p[++m]=node({t[u],l,r,1,i});
    }
    stable_sort(p+1,p+m+1,cmp1);
    cdq(1,m);
    for(int i=1;i<=q;++i)
        if(ans[i]==1e18) cout<<"Impossible"<<endl;
        else cout<<ans[i]<<endl;
    return 0;
}

:::