题解：P14588 [LNCPC 2025] 前线支援

RAND_MAX · 2026-11-08 13:59:23 · 题解

题解区怎么没我们简单易懂的根号做法。

根号做法除了常数大一点没有任何缺点。

下文默认求 LCA 复杂度 O(1)，使用 ST 表即可。所有在序列上的操作均为 dfs 序。

观察一些性质，我们发现对于一个修改，如果 y 不在 x 子树内是容易维护的，我们只需要找到 l=\operatorname{LCA}(x,y)，给 x 子树内的点加上 s_x+s_y-2s_l 即可。s_x 单独维护，后两项是区间加，都可以使用线段树简单维护。

但我们发现如果 y 在 x 子树内就不好办了，因为这时候对于 x 子树内的点 i，\operatorname{LCA}(i,y) 并不一定相同。我们称这种修改为复杂修改。

于是我们考虑根号重构。具体地，对于非复杂修改直接维护。同时每 B 次复杂修改重构一次每个点的答案，查询时枚举还未计算的复杂修改计算贡献，再加上上次重构的答案即可。

首先考虑如何 O(1) 维护一个复杂修改 (x,y) 对一个询问 u 的贡献。你发现如果 x,u 没有祖先关系那不会产生任何贡献，否则只会对两者间较深的那个点的子树产生贡献，不妨设这个点为 u。

如果 y 在 u 子树外，我们类似非复杂修改地处理。因为我们只需要求和，所以可以预处理 s_x 的前缀和，后两项直接乘子树大小即可。

如果 y 在 u 子树内，我们同样维护 s_x 前缀和，s_y 直接乘子树大小。难点在于处理 -2s_l。我们考虑拆贡献，先减去 2s_{fa_u}，这样还有一部分重复边的贡献没被减掉。考虑一条边算重的情况，发现一定在 u 到 y 的链上，且被它子树内每个点都算重。形式化地，边 (fa_i,i) 被算重当且仅当 i 在 u 到 y 的链上，并且被算重了 siz_i 次。于是我们维护树上根链 -2\times w_i\times siz_i 前缀和 S_i，查询时加上 S_y-S_{fa_u} 即可。于是我们做到了 O(1) 维护一个复杂修改 (x,y) 对一个询问 u 的贡献。

接下来考虑如何做到 O(n) 重构。s_x 与 s_y 可以直接在线段树上维护。对于 s_l，类似查询 y 在 u 子树内地，考虑每条边的贡献。这个容易用树上差分算出一条边被多少个修改包含，记其为 cnt_i。那么点 i 子树内的点都会有 -2\times cnt_i\times w_i 的贡献，O(n) 前缀和即可。注意答案统计之后要取前缀和，因为需要查询区间答案和。

我们设阈值为 B，令 n,q 同阶，则总复杂度为 O(nB+n\times\frac{n}{B}+n\log n)，取 B=\sqrt{n} 时复杂度平衡为 O(n\sqrt{n}+n\log n)，可以通过本题。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long
#define gc getchar
//char buf[1<<20],*p1,*p2;
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define R read()
using namespace std;
int read()
{
    int x=0,f=1;
    char c=gc();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=gc();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=gc();
    return x*f;
}
void write(int x,char xx)
{
    static int st[35],top=0;
    if(x<0){x=-x;putchar('-');}
    do
    {
        st[top++]=x%10,x/=10;
    }while(x);
    while(top) putchar(st[--top]+48);
    putchar(xx);
}
#define N 500010
int n,Q,fa[N],s[N],dfn[N],tot,id[N],siz[N],w[N],dep[N],st[21][N];
vector<int>g[N];
inline int op(int x,int y){return dep[x]<dep[y]?x:y;}
void dfs(int x)
{
    siz[x]=1,s[x]=s[fa[x]]+w[x],dep[x]=dep[fa[x]]+1,dfn[x]=++tot,id[tot]=x;
    for(auto i:g[x]) dfs(i),siz[x]+=siz[i];
}
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (tr[u].l+tr[u].r>>1)
struct node{int l,r,su,lz1,cnt,suu,lz2;}tr[N<<2];
inline void upd(int u){tr[u].su=tr[ls].su+tr[rs].su,tr[u].suu=tr[ls].suu+tr[rs].suu;}
inline void c(int u,int x){tr[u].su+=(tr[u].r-tr[u].l+1)*x,tr[u].lz1+=x;}
inline void cc(int u,int x){tr[u].suu+=tr[u].cnt*x,tr[u].lz2+=x;}
inline void pd(int u)
{
    if(tr[u].lz1){c(ls,tr[u].lz1),c(rs,tr[u].lz1),tr[u].lz1=0;}
    if(tr[u].lz2){cc(ls,tr[u].lz2),cc(rs,tr[u].lz2),tr[u].lz2=0;}
}
void build(int u,int l,int r)
{
    tr[u]={l,r};
    if(l==r) return tr[u].cnt=s[id[l]],void(0);
    build(ls,l,mid),build(rs,mid+1,r),tr[u].cnt=tr[ls].cnt+tr[rs].cnt;
}
void add(int u,int l,int r,int x)
{
    if(l<=tr[u].l&&tr[u].r<=r) return c(u,x);
    pd(u),(l<=mid&&(add(ls,l,r,x),1)),(r>mid&&(add(rs,l,r,x),1)),upd(u);
}
void Add(int u,int l,int r,int x)
{
    if(l<=tr[u].l&&tr[u].r<=r) return cc(u,x);
    pd(u),(l<=mid&&(Add(ls,l,r,x),1)),(r>mid&&(Add(rs,l,r,x),1)),upd(u);
}
pii que(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r) return {tr[u].su,tr[u].suu};
    pd(u);
    pii res={0,0};
    if(l<=mid){pii t=que(ls,l,r);res.fi+=t.fi,res.se+=t.se;}
    if(r>mid){pii t=que(rs,l,r);res.fi+=t.fi,res.se+=t.se;}
    return res;
}
#undef ls
#undef rs
#undef mid
inline bool in(int x,int y){return !(dfn[y]<dfn[x]||dfn[y]>=dfn[x]+siz[x]);}
int lca(int u,int v)
{
    if(dfn[u]>dfn[v]) swap(u,v);
    if(in(u,v)) return u;
    u=dfn[u],v=dfn[v];
    int s=__lg(v-u+1);
    return fa[op(st[s][u],st[s][v-(1<<s)+1])];
}
int dis(int x,int y){return s[x]+s[y]-2*s[lca(x,y)];}
int B,ans[N],W[N],S[N],SS[N];
vector<pii>v;
void reb()
{
    for(int i=n;i>=1;i--) ans[i]-=ans[i-1],W[i]=0;
    for(auto&[x,y]:v) W[y]++,W[fa[x]]--,add(1,dfn[x],dfn[x]+siz[x]-1,s[y]-2*s[fa[x]]),Add(1,dfn[x],dfn[x]+siz[x]-1,1);
    for(int i=n;i>=1;i--) W[fa[id[i]]]+=W[id[i]];
    for(int i=1;i<=n;i++) W[i]=W[i]*2*w[i];
    W[0]=0;
    for(int i=1;i<=n;i++) W[id[i]]+=W[fa[id[i]]];
    v.clear();
    for(int i=1;i<=n;i++) ans[i]+=ans[i-1]+W[id[i]];
}
int Qu(int x)
{
    int sum=-(ans[dfn[x]+siz[x]-1]-ans[dfn[x]-1]);
    for(auto[u,y]:v) if(in(u,x)||in(x,u)) 
    {
        u=(in(u,x)?x:u);
        if(in(u,y)) sum+=siz[u]*(s[y]-2*s[fa[u]])+S[dfn[u]+siz[u]-1]-S[dfn[u]-1]-SS[y]+SS[fa[u]];
        else sum+=siz[u]*(s[y]-2*s[lca(u,y)])+S[dfn[u]+siz[u]-1]-S[dfn[u]-1];
    }
    pii t=que(1,dfn[x],dfn[x]+siz[x]-1);
    return t.fi+t.se+sum;
}
void solve()
{
    n=R,Q=R,B=sqrt(n)+1;
    for(int i=2;i<=n;i++) fa[i]=R,w[i]=R,g[fa[i]].pb(i);
    dfs(1),build(1,1,n);
    for(int i=1;i<=n;i++) st[0][i]=id[i],S[i]=S[i-1]+s[id[i]],SS[i]=2*siz[i]*w[i];
    for(int i=1;i<=n;i++) SS[id[i]]+=SS[fa[id[i]]];
    int LG=__lg(n);
    for(int j=1;j<=LG;j++) for(int i=1;i+(1<<j)-1<=n;i++) st[j][i]=op(st[j-1][i],st[j-1][i+(1<<j-1)]);
    while(Q--)
    {
        int op=R,x=R,y;
        if(op==1) 
        {
            y=R;
            if(!in(x,y)) add(1,dfn[x],dfn[x]+siz[x]-1,s[y]-2*s[lca(x,y)]),Add(1,dfn[x],dfn[x]+siz[x]-1,1);
            else v.pb({x,y});
        }
        else write(Qu(x),'\n');
        if((int)v.size()>B) reb();
    }
}
int T=1;
signed main()
{
    // freopen("rescue.in","r",stdin);
    // freopen("rescue.out","w",stdout);
    // T=R;
    while(T--) solve();
    return 0;
}