洛谷 - P6329 震波

传送门：洛谷 - P6329

思路分析

维护一个点小于等于$k$的路径的贡献可以用线段树或树状数组维护
建立出点分树，每个节点维护两个信息，$s1$表示该点子树的贡献，$s2$表示该点子树对该点父亲的贡献，用来容斥

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const int N = 1e5+10;


struct BIT {
    vector<int>b;
    void build(int n) {
        for(int i=0; i<n+5; i++) b.pb(0);
    }

    void add(int x,int k) {
        x++;
        for(int i=x; i<sz(b); i+=lowbit(i)) b[i]+=k;
    }

    int get(int x) {
        x++;
        int ans = 0;
        x = min(x,(int)sz(b)-1);
        for(int i=x; i; i-=lowbit(i)) ans+=b[i];
        return ans;
    }
} s1[N],s2[N];


vector<int>e[N];

struct Grand_Father {
    int deep[N], euler[N << 1], esiz, rid[N],log_2[N<<1];
    void dfs(int u, int fa) {
        deep[u] = deep[fa] + 1;
        rid[u] = esiz + 1;
        for(auto v:e[u]) {
            if(v == fa) continue;
            euler[++esiz] = u;
            dfs(v, u);
        }
        euler[++esiz] = u;
    }
    int mn[N << 1][23];

    inline void rmq_init() {
        if(!log_2[2]) for(int i=2; i<N*2; i++) log_2[i] = log_2[i >> 1] + 1;
        for(int i=1; i<=esiz; i++) mn[i][0] = euler[i];
        for(int j=1; (1 << j) <= esiz; j++) {
            for(int i=1; i + (1 << j) - 1 <= esiz; i++) {
                if(deep[mn[i][j - 1]] < deep[mn[i + (1 << (j - 1))][j - 1]]) mn[i][j] = mn[i][j - 1];
                else mn[i][j] = mn[i + (1 << (j - 1))][j - 1];
            }
        }
    }
    void solve(int s) {
        esiz = 0;
        dfs(s, 0);
        rmq_init();
    }
    inline int rmq(int l, int r) {
        int det = r - l + 1, kk = log_2[det];
        if(deep[mn[l][kk]] <= deep[mn[r - (1 << kk) + 1][kk]]) return mn[l][kk];
        else return mn[r - (1 << kk) + 1][kk];
    }
    inline int lca(int u, int v) {
        int l = rid[u], r = rid[v];
        if(l > r) swap(l, r);
        return rmq(l, r);
    }
    inline int dis(int u, int v) {
        return deep[u] + deep[v] - 2 * deep[lca(u,v)];
    }
} LCA;

int dis(int x,int y){
    return LCA.dis(x,y);
}

int siz[N],tot,root,maxp[N],dfa[N];
bool vis[N];

void getroot(int u,int f) {
    siz[u] = 1;
    maxp[u] = 0;
    for(auto v:e[u]) {
        if(v==f || vis[v]) continue;
        getroot(v,u);
        siz[u]+=siz[v];
        maxp[u] = max(maxp[u],siz[v]);
    }
    maxp[u] = max(maxp[u],tot-siz[u]);
    if(maxp[u]<maxp[root]) root = u;
}


void div(int u) {
    vis[u] = true;
    int all = tot; 
    s1[u].build(tot);
    s2[u].build(tot);
    for(auto v:e[u]) {
        if(vis[v]) continue;
        tot=siz[v]>siz[u]? all - siz[u]:siz[v];
        root=0;
        maxp[root] = tot;
        getroot(v,u);
        dfa[root] = u;
        div(root);
    }
}

void modify(int idx,int val){
    int now = idx;
    while(now){
        int f = dfa[now];
        s1[now].add(dis(now,idx),val);
        if(f) s2[now].add(dis(f,idx),val);
        now = f;
    }
}

int query(int idx,int k){
    int ans = 0;
    int now = idx,last = 0;
    while(now){
        int d = dis(idx,now);
        if(d>k){
            last = now;
            now = dfa[now];
            continue;
        }
        ans+=s1[now].get(k-d);
        if(last) ans-=s2[last].get(k-d);
        last = now;
        now = dfa[now];
    }
    return ans;
}

int n,m;
int a[N];

void init() {
    LCA.solve(1);
    root = 0;
    tot = n;
    maxp[root] = tot;
    getroot(1,1);
    div(root);
    for(int i=1;i<=n;i++) modify(i,a[i]);
}


signed main() {

#ifdef xiaofan
    freopen("2.in","r",stdin);
    freopen("m1.out","w",stdout);
#endif

    
    read(n,m);
    for(int i=1; i<=n; i++) read(a[i]);
    for(int i=1; i<n; i++) {
        int u,v;
        read(u,v);
        e[u].pb(v);
        e[v].pb(u);
    }
    init();
    int ans = 0;
    for(int i=1;i<=m;i++){
        int op,x,y;
        read(op,x,y);
        x^=ans;
        y^=ans;
        if(op==0){
            ans = query(x,y);
            printf("%d\n",ans);
        }else{
            modify(x,y-a[x]);
            a[x] = y;
        }
    }



    return 0;
}