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

Wei_Han · 2026-07-28 13:22:57 · 题解

vp 的时候以为 y 只能在子树外，写了半天发现读错题了，然后又被搬到模拟赛了，以为查询是单点，写了半天发现又读错题了。

分情况讨论一下。

为了方便表示，记下一个查询点为 z，z 子树里有一个点 p，这里暂时默认 z 在 x 子树内。

y 在 x 子树外

显然此时对所有 z 可以分为两段贡献，p \to z 和 z \to y，p \to z 可以表示为 \text{dep}_p - \text{dep}_z，预处理所有 \text{dep}_p 的和，然后维护 x 子树内所有 z 被加了几遍即可，用一个 BIT 可以完成。

对于 z \to y 部分，可以表示为 \text{dep}_z + \text{dep}_y - 2\text{dep}_{\operatorname{LCA}(z,y)}，因为 \operatorname{LCA}(z,y) = \operatorname{LCA}(x,y)，所以显然后面两项都是常量，对 x 做子树加法即可，\text{dep}_z 维护一下被加的次数即可。

y 在 x 子树内

显然此时的难点在于 x \to y 的路径上子树内的点。

考虑直接算 \text{dep}_z + \text{dep}_y - 2\text{dep}_x，此时算多了图中的蓝色段，假设 x 子树内所有点都这样算，把多余的贡献划分到每条边上，显然此时一条蓝色边的多余贡献是 \text{siz}_i \times w_i，那么，我们只需要知道这些蓝色边被重复算的次数即可，拿一个线段树可以简单维护。具体地，维护一下区间 \text{siz} \times w 的和即可。

上述我们只考虑了 z 在 x 子树内的情况，考虑 z 在 x 子树外，或者说，z 的子树内发生了操作一，z 的值怎样变化。

对于 y 在 x 子树内，只需要让 x 父亲到根的每个点加上 \sum (\text{dep}_z + (\text{dep}_y - 2\text{dep}_{\operatorname{LCA}(x,y)}))，这个和上述相同的即可。

对于 y 在 x 子树外的情况，我们可仿照上述加上 \sum (\text{dep}_z + (\text{dep}_y - 2\text{dep}_{x}))，只是我们暂时先不处理蓝色的冗余部分，放到查询时统一处理。

查询时，考虑如果子树内有若干被打上标记的边，那么其带来的贡献是 -\text{siz}_i \times w_i，这个是容易统计的，所以所有步骤都可以完成了，复杂度 O(n\log^2 n)。

:::info[代码]

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pr putchar(10)
#define fi first
#define se second
#define pp putchar(' ')
#define pii pair<ll,ll>
#define tri tuple<ll,ll,ll>
#define gt(k,x) (get<k>(x))
#define pdi pair<double,ll>
#define mem(aa,bb) memset(aa,bb,sizeof(aa))
#define fo(a,i,b) for(ll i = (a) ; i <= (b) ; ++ i )
#define Fo(a,i,b) for(ll i = (a) ; i >= (b) ; -- i )
#define pb push_back
#define reg register
#define eb emplace_back
#define bct __builtin_popcount 
#define mk make_pair
#define IT iterator
#define all(x) x.begin(),x.end()
#define lbd lower_bound
#define ubd upper_bound
#define lowbit(x) ((x)&(-(x)))
#define gb(x,i) (((x)>>i)&1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define deb(a...) [&](auto...b){char s[]=" , ,"#a;strtok(s,",");((cerr<<strtok(0,",")<<"="<<b<<"; "),...)<<endl;}(__LINE__,a)
//#pragma GCC optimize(2)
using namespace std;
bool ST;

typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef unsigned long long ull;
typedef __int128 i128;
typedef __uint128_t u128;
typedef double db;

typedef int ll;
// typedef long long ll;
// typedef __int128 ll;

#define getchar getchar_unlocked
#define putchar putchar_unlocked

const ll mod=1e9+7;
template <class T> inline bool ckmn(T &a,T b){return a>b?a=b,1:0;}
template <class T> inline bool ckmx(T &a,T b){return a<b?a=b,1:0;}
template <class T> inline void _A(T &x,T y){x=(x+y>=mod?x+y-mod:x+y);}
template <class T> inline void _M(T &x,T y){x=1ll*x*y%mod;}
template <class T> inline T A_(T x,T y){return (x+y>=mod?x+y-mod:x+y);}
template <class T> inline T M_(T x,T y){return 1ll*x*y%mod;}
template <class T> inline void read(T &s)
{
   s=0;reg int f=1;reg char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
   while(isdigit(c))s=(s<<3)+(s<<1)+(c^48),c=getchar();s*=f;return;
}
template <class T> inline void wr(T x)
{
   if(x<0)putchar('-'),x=-x;int buf[21],top=0;while(x)buf[++top]=x%10,x/=10;
   if(!top)buf[++top]=0;while(top)putchar(buf[top--]^'0');return;
}
template <class T, class ...A> inline void read(T &x,A &...a){read(x);read(a...);}
template <class T, class ...A> inline bool ckmn(T &x,T y,A ...a){return ckmn(x,y)|ckmn(x,a...);}
template <class T, class ...A> inline bool ckmx(T &x,T y,A ...a){return ckmx(x,y)|ckmx(x,a...);}
template <class T, class ...A> inline void _A(T &x,T y,A ...a){_A(x,y),_A(x,a...);}
template <class T, class ...A> inline void _M(T &x,T y,A ...a){_M(x,y),_M(x,a...);}
template <class T, class ...A> inline T A_(T x,T y,A ...a){return A_(A_(x,y),a...);}
template <class T, class ...A> inline T M_(T x,T y,A ...a){return M_(M_(x,y),a...);}

const ll _N=1e6+5;ll Pre[_N],Inv[_N];
inline ll qpow(ll a,ll b){return !b?1ll:M_(1ll*qpow(M_(a,a),b>>1ll),((b&1ll)?a:1ll));}
inline ll C(ll n,ll m){return (n<m||n<0||m<0)?0ll:M_(Pre[n],Inv[m],Inv[n-m]);}
inline void InitC(ll n){Pre[0]=1;fo(1,i,n) Pre[i]=M_(Pre[i-1],i);Inv[n]=qpow(Pre[n],mod-2);Fo(n-1,i,1) Inv[i]=M_(Inv[i+1],(i+1));Inv[0]=1;}

const ll N=1e6+5,M=1e5+5;
ll n,q,op,x,y,fa[N],w,dep[N],son[N],siz[N],top[N],id[N],rid[N],dis[N],cnt;i64 sumdep[N],lca;vector<pii> g[N];
struct BIT
{
    i64 bit[N];
    inline void upd(ll i,i64 k){for(;i<=n;i+=lowbit(i)) bit[i]+=k;}
    inline i64 qry(ll i){if(i<=0) return 0;i64 ans=0;for(;i;i-=lowbit(i)) ans+=bit[i];return ans;}
    inline void upd(ll l,ll r,i64 k){upd(l,k),upd(r+1,-k);}
}bit,bit1,bit2;
struct SGT{ll l,r,lz;i64 sum,ssum,sm,ssm;}tree[N<<2];
#define rt tree[root]
#define ls tree[root<<1]
#define rs tree[root<<1|1]
inline void build(ll root,ll l,ll r){rt.l=l,rt.r=r;if(l==r) return rt.sm=dis[rid[l]],rt.ssm=dis[rid[l]]*siz[rid[l]],void();ll mid=l+r>>1;build(root<<1,l,mid),build(root<<1|1,mid+1,r),rt.sm=ls.sm+rs.sm,rt.ssm=ls.ssm+rs.ssm;}
inline void mdf(ll root,i64 k){rt.sum+=k*rt.sm,rt.ssum+=k*rt.ssm,rt.lz+=k;}
inline void pd(ll root){if(rt.lz) mdf(root<<1,rt.lz),mdf(root<<1|1,rt.lz),rt.lz=0;}
inline void upd(ll root,ll x,ll y,i64 k){ll l=rt.l,r=rt.r;if(x<=l&&y>=r) return mdf(root,k);ll mid=l+r>>1;pd(root);if(x<=mid) upd(root<<1,x,y,k);if(y>mid) upd(root<<1|1,x,y,k);rt.sum=ls.sum+rs.sum,rt.ssum=ls.ssum+rs.ssum;}
inline i64 qry(ll root,ll x,ll y){ll l=rt.l,r=rt.r;if(x<=l&&y>=r) return rt.sum;ll mid=l+r>>1;i64 ans=0;pd(root);if(x<=mid) ans+=qry(root<<1,x,y);if(y>mid) ans+=qry(root<<1|1,x,y);return ans;}
inline i64 qry1(ll root,ll x,ll y){if(x>y) return 0;ll l=rt.l,r=rt.r;if(x<=l&&y>=r) return rt.ssum;ll mid=l+r>>1;i64 ans=0;pd(root);if(x<=mid) ans+=qry1(root<<1,x,y);if(y>mid) ans+=qry1(root<<1|1,x,y);return ans;}
inline void dfs1(ll x,ll f,ll d){dep[x]=d,siz[x]=1,sumdep[x]=dep[x];for(auto [y,w]:g[x]) if(y!=f){dfs1(y,x,d+w),sumdep[x]+=sumdep[y],dis[y]=w,siz[x]+=siz[y];if(siz[y]>siz[son[x]]) son[x]=y;}}
inline void dfs2(ll x,ll nt){top[x]=nt,id[x]=++cnt,rid[cnt]=x;if(!son[x])return;dfs2(son[x],nt);for(auto [y,w]:g[x]) if(y!=son[x]&&y!=fa[x]) dfs2(y,y);}
inline ll LCA(ll x,ll y){while(top[x]^top[y]) dep[top[x]]<dep[top[y]]?y=fa[top[y]]:x=fa[top[x]];return dep[x]<dep[y]?x:y;}
inline void upd_chain(ll x,ll y,ll k)
{
    while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        upd(1,id[top[x]],id[x],k),x=fa[top[x]];
    }if(dep[x]<dep[y]) swap(x,y);x!=y?upd(1,id[y]+1,id[x],k),1:1;
}
inline void upd1_chain(ll x,ll y,i64 k)
{
    if(!y)return;while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        bit.upd(id[top[x]],id[x],k),x=fa[top[x]];
    }if(dep[x]<dep[y]) swap(x,y);bit.upd(id[y],id[x],k);
}
inline i64 qry_chain(ll x,ll y)
{
    i64 ans=0;while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans+=qry(1,id[top[x]],id[x]),x=fa[top[x]];
    }if(dep[x]<dep[y]) swap(x,y);ans+=qry(1,id[y],id[x]);return ans;
}
bool ED;
signed main(){
    // freopen("rescue.in","r",stdin);
    // freopen("rescue.out","w",stdout);
    read(n,q);fo(2,i,n) read(fa[i],w),g[fa[i]].pb(mk(i,w)),g[i].pb(mk(fa[i],w));
    dfs1(1,0,0);dfs2(1,1),build(1,1,n);fo(1,i,q)
    {
        read(op,x);if(op==1) read(y);
        if(op==1)
        {
            if(id[y]>=id[x]&&id[y]<=id[x]+siz[x]-1) bit1.upd(id[x],id[x]+siz[x]-1,1),bit2.upd(id[x],id[x]+siz[x]-1,dep[y]-dep[x]*2),upd_chain(x,y,-2),
                upd1_chain(1,fa[x],sumdep[x]-2ll*siz[x]*dep[x]+1ll*dep[y]*siz[x]);
            else lca=dep[y]-2*dep[LCA(x,y)],bit1.upd(id[x],id[x]+siz[x]-1,1),bit2.upd(id[x],id[x]+siz[x]-1,lca),upd1_chain(1,fa[x],sumdep[x]+lca*siz[x]);
        }
        else wr(sumdep[x]*bit1.qry(id[x])+bit2.qry(id[x])*siz[x]+qry_chain(1,x)*siz[x]+qry1(1,id[x]+1,id[x]+siz[x]-1)+bit.qry(id[x])),pr;
    }

    cerr << "Time: " << (double)clock()/CLOCKS_PER_SEC << "s\n";
    cerr << "Memory: " << abs(&ST - &ED) / 1024.0 / 1024.0 << " MB\n";
    return 0;
}

:::