题解：P9336 [Ynoi2001] 梦想歌

limingyuan333 · 2026-08-06 16:26:24 · 题解

从部分分前往正解，给一种暴力维护的方法。

暴力：

暴力你对每个位置维护集合和和代表元，每次合并即可。

链：

我们发现一个性质，如果从当前位置向上与父亲合并时，若父亲权值更大父亲的代表元才是父亲，否则就是当前位置的代表元。

不难发现一次这样的改变至少让集合权值翻倍，题目限制了总和，于是，如果可以每次可以直接找到下一个变换的位置就可以暴力做完。

但是我们发现可能这样的位置还是不太好找，因为没有什么相邻两个数的差没有单调性。我们不妨将条件松一些，找到可能改变的位置。

具体点，我们找到到根链上第一个子树权值和大于等于当前两倍的节点，这个节点可能是改变点，我们只需要暴力 chk 这个位置和上一个位置的权值即可，这样最多跳 \log V 次，每次 \log n chk。修改时只需树剖改一下每个点的子树和即可。复杂度是 O(q \log n \log V)。

正解：

O(q \log ^2 V \log n )

考虑树和链之间有什么不同之处。树的话你每次需要从每个儿子 chk，链则只有一个点。每次修改的时候只会影响到到根链的答案，我们考虑每次修改这条到根链的答案。

我们发现当前节点的子树和乘二如果大于父亲的子树和，那么这个点一定可以获胜，因为哪怕其他所有点都在一个子树内，值都没有这个点大，于是我们可以先考虑暴力往上跳然后用刚才链类似方法维护子树和然后再线段树上二分找到子树和大于等于当前子树和乘二的位置，这里复杂度显然是 \log V \times \log n。

然后我们找到这个点之后，我们考虑直接暴力修改这个点的答案，即从他的儿子中每次找到对于儿子中前缀和翻倍的那个点，这样显然同样是 \log V，所以只要维护出儿子之间按编号顺序的前缀和，之后再线段树上二分即可。

我们现在相当于想要保持树剖复杂度又想维护链和，领域的和。经典的，我们可以使用毛毛虫树剖，即我们每次先给重儿子标号之后再顺次给所有轻儿子依次标号，这样就可以使每条重链和领域信息都是连续的，注意这样标号的话，每条重链链头和链不一定连续，每个点的重儿子和其他轻儿子不一定连续，这个你直接特殊处理一下就可以了。

于是通过上面操作我们就可以在 O(q \log ^2 V \log n ) 时间内通过这道题。看着很大其实感觉一下应该是跑不满的，虽然还是很慢，下面给一个不保证任何时候都可以通过的代码。

O(q \log V \log n )

发现维护邻域也太慢了要多一个 \log V，我们发现每次我们只是两个集合在合并，前 i 个儿子具体是什么与后面的没有任何关系，我们只要前 i 个儿子的代表元和权值是多少。

于是我们考虑点三度化。按儿子编号从小往大把两个点新建一个点当父亲，然后再依次合并，我们发现这样就变成了二叉树，不用维护领域，每次暴力查父亲和左右儿子就可以了，复杂度 O(q \log V \log n )，这个代码没写。

代码：

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fr first
#define sc second
#define ll long long
using namespace std;
const int MAXN=2e5+10;
int n,m,fa[MAXN],sz[MAXN],is[MAXN],dep[MAXN];
int id[MAXN],top[MAXN],son[MAXN],dfn[MAXN],idx;
namespace Fastio {
const int L = 1 << 20;
inline char gc() {
    static char buf[L], *l = buf, *r = buf;
    if (__builtin_expect(l == r, 0))
        r = (l = buf) + fread(buf, 1, L, stdin);
    return (l == r) ? EOF : *l++;
}
char obuf[L], *p = obuf;
inline void pc(char c) {
    if (p == obuf + L)
        fwrite(obuf, 1, L, stdout), p = obuf;
    *p++ = c;
}
inline void flush() { fwrite(obuf, 1, p - obuf, stdout); }
struct Reader {
    template <typename T>
    inline Reader& operator>>(T& x) {
        x = 0;int f = 1;
        char c = gc();
        while (!isdigit(c)) f *= (c == '-' ? -1 : 1), c = gc();
        while (isdigit(c)) x = 10 * x + (c - '0'), c = gc();
        x *= f;
        return *this ;
    }
    Reader() {}
} cin;
struct Writer {
    template <typename T>
    inline Writer& operator<<(T x) {
        static short tp = 0, s[40];
        do
            s[++tp] = x % 10, x /= 10;
        while (x);
        while (tp) pc(s[tp--] + '0');
        return *this;
    }
    inline Writer& operator<<(const char* s) {
        int i = 0;
        while (s[i]) pc(s[i++]);
        return *this;
    }
    inline Writer& operator<<(char c) {
        pc(c);
        return *this;
    }
    Writer() {}
    ~Writer() { flush(); }
} cout;
#define cin Fastio::cin
#define cout Fastio::cout
}
vector<int>vec[MAXN];
void dfs1(int now){
    sz[now]=1;dep[now]=dep[fa[now]]+1;
    for(int to:vec[now]){
        dfs1(to);sz[now]+=sz[to];
        if(sz[son[now]]<sz[to]) son[now]=to;
    }is[son[now]]=1;
}
int in[MAXN],out[MAXN],pos[MAXN];
void dfs2(int now){
    if(is[now]) id[dfn[now]=++idx]=now;
    if(son[now]){
        top[son[now]]=top[now];
        dfs2(son[now]);
    }in[now]=idx+1;
    for(int to:vec[now]){
        if(to==son[now]){pos[now]=idx;continue;}
        id[dfn[to]=++idx]=to;
    }out[now]=idx;
    for(int to:vec[now]){
        if(to==son[now]) continue;
        top[to]=to;dfs2(to);
    }
}
int f[MAXN];
ll w[MAXN],a[MAXN];
void dfs3(int now){
    w[now]=a[now],f[now]=now;
    for(int to:vec[now]){
        dfs3(to);
        if(w[now]<w[to]) f[now]=f[to];
        w[now]+=w[to];
    }
}
struct SGT{
    ll t[MAXN<<2],tag1[MAXN<<2],w[MAXN<<2],tag3[MAXN<<2];
    int ans[MAXN<<2],tag2[MAXN<<2];
    inline void down_add(int p,ll v){
        tag1[p]+=v;t[p]+=v;
    }
    inline void down_cov(int p,int v){
        tag2[p]=v;ans[p]=v;
    }
    inline void down_Add(int p,ll v){
        tag3[p]+=v;w[p]+=v;
    }
    inline void push_down(int p){
        if((!tag1[p])&&(!tag2[p])&&(!tag3[p])) return ;
        if(tag1[p]) down_add(p<<1,tag1[p]),down_add(p<<1|1,tag1[p]);
        if(tag2[p]) down_cov(p<<1,tag2[p]),down_cov(p<<1|1,tag2[p]);
        if(tag3[p]) down_Add(p<<1,tag3[p]),down_Add(p<<1|1,tag3[p]);
        tag1[p]=tag2[p]=tag3[p]=0;
    }
    inline void push_up(int p){
        t[p]=max(t[p<<1],t[p<<1|1]);
        w[p]=max(w[p<<1],w[p<<1|1]);
    }
    inline void build(int p,int l,int r){
        if(l==r) return ans[p]=f[id[l]],void();
        int mid=l+r>>1;
        build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    }
    inline void update(int p,int l,int r,int x,int y,ll w){
        if(x<=l&&r<=y) return down_add(p,w);
        int mid=l+r>>1;push_down(p);
        if(x<=mid) update(p<<1,l,mid,x,y,w);
        if(y>mid) update(p<<1|1,mid+1,r,x,y,w);
        push_up(p);
    }
    inline void Add(int p,int l,int r,int x,int y,ll w){
        if(x<=l&&r<=y) return down_Add(p,w);
        int mid=l+r>>1;push_down(p);
        if(x<=mid) Add(p<<1,l,mid,x,y,w);
        if(y>mid) Add(p<<1|1,mid+1,r,x,y,w);
        push_up(p);
    }
    inline void Cover(int p,int l,int r,int x,int y,int w){
        if(x<=l&&r<=y) return down_cov(p,w);
        int mid=l+r>>1;push_down(p);
        if(x<=mid) Cover(p<<1,l,mid,x,y,w);
        if(y>mid) Cover(p<<1|1,mid+1,r,x,y,w);
        push_up(p);
    } 
    inline int ask(int p,int l,int r,int x){
        if(l==r) return ans[p];
        int mid=l+r>>1;push_down(p);
        return (x<=mid?ask(p<<1,l,mid,x):ask(p<<1|1,mid+1,r,x));
    }
    inline ll ask_v(int p,int l,int r,int x){
        if(l==r) return t[p];
        int mid=l+r>>1;push_down(p);
        return (x<=mid?ask_v(p<<1,l,mid,x):ask_v(p<<1|1,mid+1,r,x));
    }
    inline ll qry(int p,int l,int r,int x){
        if(l==r) return w[p];
        int mid=l+r>>1;push_down(p);
        return (x<=mid?qry(p<<1,l,mid,x):qry(p<<1|1,mid+1,r,x));
    }
    inline int find1(int p,int l,int r,int x,int y,ll v){
        if(w[p]<v) return -1;
        if(l==r) return l;
        push_down(p);
        int mid=l+r>>1;int rs=-1;
        if(x<=mid) rs=find1(p<<1,l,mid,x,y,v);
        if(rs==-1&&y>mid) rs=find1(p<<1|1,mid+1,r,x,y,v);
        return rs;
    }
    inline int find2(int p,int l,int r,int x,int y,ll v){
        if(t[p]<v) return -1;
        if(l==r) return l;
        push_down(p);
        int mid=l+r>>1;int rs=-1;
        if(y>mid) rs=find2(p<<1|1,mid+1,r,x,y,v);
        if(rs==-1&&x<=mid) rs=find2(p<<1,l,mid,x,y,v);
        return rs;
    }
}sgt;
static inline void upd(int x,ll v){
    while(x){
        int tp=top[x];
        if(x!=tp) sgt.update(1,1,n,dfn[son[tp]],dfn[x],v);
        x=tp;sgt.update(1,1,n,dfn[x],dfn[x],v);
        if(fa[x]) sgt.Add(1,1,n,dfn[x],out[fa[x]],v);
        x=fa[x];

    }
}
static inline int solve(int x){
    ll w=a[x];int num=x;
    int now=in[x];
    if(!son[x]) return x;
    ll v=sgt.ask_v(1,1,n,dfn[son[x]]);
    while(now<=pos[x]){
        int nxt=sgt.find1(1,1,n,now,pos[x],((w-a[x])<<1)+a[x]);
        if(nxt==-1) now=pos[x]+1;
        else{
            ll val=a[x],s=sgt.ask_v(1,1,n,nxt);
            if(nxt!=in[x]) val+=sgt.qry(1,1,n,nxt-1); 
            if(s>val) num=id[nxt];
            now=nxt+1;w=s+val;
        }
    }
    ll val=a[x];
    if(pos[x]>=in[x]) val+=sgt.qry(1,1,n,pos[x]);
    if(val<v) num=son[x];w=val+v;
    while(now<=out[x]){
        int nxt=sgt.find1(1,1,n,now,out[x],((w-a[x]-v)<<1)+a[x]+v);
        if(nxt==-1) now=out[x]+1;
        else{
            ll val=a[x]+v,s=sgt.ask_v(1,1,n,nxt);
            if(nxt!=in[x]) val+=sgt.qry(1,1,n,nxt-1);
            if(s>val) num=id[nxt];
            now=nxt+1;w=s+val;
        }
    }
    return num;
}
static inline void Upd(int x,int y,int v){
    if(x==y) return ;
    while(x){
        int Son=son[top[x]];
        int l=dfn[Son],r=dfn[x];
        if(dep[x]<dep[y]) break;
        if(x!=top[x]){
            if(dep[Son]<=dep[y]){sgt.Cover(1,1,n,dfn[y],r,v);break;}
            sgt.Cover(1,1,n,l,r,v);
        }x=top[x];sgt.Cover(1,1,n,dfn[x],dfn[x],v);
        x=fa[x];
    }
}
static inline void Solve(int x){
    ll w=a[x];int pre=x;
    pii lst={x,x};
    while(x){
        int l=dfn[son[top[x]]],r=dfn[x];
        if(x!=top[x]){
            ll w2=sgt.ask_v(1,1,n,l);
            if(w2>=(w<<1)){
                int c=sgt.find2(1,1,n,l,r,w<<=1);
                pre=solve(id[c]);w=sgt.ask_v(1,1,n,c);
                Upd(lst.fr,id[c],lst.sc==lst.fr?lst.fr:sgt.ask(1,1,n,dfn[lst.sc]));
                lst={id[c],pre};x=fa[id[c]];
            }else x=top[x],w=w2;
        }
        if(x==top[x]){
            ll w2=sgt.ask_v(1,1,n,dfn[x]);
            if((w2>=(w<<1))){
                pre=solve(x);
                Upd(lst.fr,x,lst.sc==lst.fr?lst.fr:sgt.ask(1,1,n,dfn[lst.sc]));
                lst={x,pre};
            }w=w2;x=fa[x];
        }
    }

    if(lst.fr==1) sgt.Cover(1,1,n,1,1,lst.sc==1?1:sgt.ask(1,1,n,dfn[lst.sc]));
    else Upd(lst.fr,1,lst.sc==lst.fr?lst.fr:sgt.ask(1,1,n,dfn[lst.sc]));
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++){
        cin>>fa[i];vec[fa[i]].push_back(i);
    }dfs1(1);is[1]=top[1]=1;dfs2(1);dfs3(1);
    sgt.build(1,1,n);
    for(int i=1;i<=n;i++) upd(i,a[i]);
    while(m--){ 
        int op,x;ll v;cin>>op>>x;
        if(op&1) cout<<a[sgt.ask(1,1,n,dfn[x])]<<'\n';
        else{
            cin>>v;a[x]+=v;
            upd(x,v);Solve(x);
        }
    }
    return 0;
}