12682 Tree

树链剖分题。
1e9数开6次根号后就变成1了,所以我们可以维护区间最大值,当最大值小于等于1时,就不用更新这段区间了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn  = 100005;
vector<int> mmp[maxn];
int top[maxn],fa[maxn],dep[maxn],sz[maxn],id[maxn],rev[maxn],cnt;
ll sum[maxn<<2],mx[maxn<<2],a[maxn];

inline void push_up(int rt) {
    sum[rt] = sum[rt*2] + sum[rt*2+1];
    mx[rt] = max(mx[rt*2] , mx[rt*2+1]);
}

void build(int rt,int l,int r) {
    if (l==r) {
        sum[rt] = mx[rt] = a[rev[l]];
    } else {
        int mid = (l+r)/2;
        build(rt*2,l,mid);
        build(rt*2+1,mid+1,r);
        push_up(rt);
    }
}

void update(ll rt,ll l,ll r,ll L,ll R) {
//    if (rt==1) cout<<"update "<<L<<" "<<R<<endl;
    if (mx[rt]<=1) return;
    if (r<L||l>R) return;
    if (l==r) {
        sum[rt] = mx[rt] = floor(sqrt(mx[rt]));
//        cout<<"update "<<l<<" val="<<mx[rt]<<endl;
    } else {
        int mid = (l+r)/2;
        if (L<=mid) update(rt*2,l,mid,L,R);
        if (mid<R) update(rt*2+1,mid+1,r,L,R);
        push_up(rt);
    }
}

ll query(ll rt,ll l,ll r,ll L,ll R) {
    if (L<=l&&r<=R) {
        return sum[rt];
    } else {
        ll ans = 0,mid=(l+r)/2;
        if (L<=mid) ans += query(rt*2,l,mid,L,R);
        if (mid<R) ans += query(rt*2+1,mid+1,r,L,R);
        return ans;
    }
}

int dfs1(int x,int f,int d) {
    fa[x] = f;
    dep[x] =d;
    sz[x] = 1;
    for (int y : mmp[x]) {
        if (y==f) continue;
        dfs1(y,x,d+1);
        sz[x] += sz[y];
    }
    return 0;
}

int dfs2(int x,int f,int tp) {
//    cout<<"dfs2 "<<x<<" "<<f<<" "<<tp<<endl;
    top[x] = tp;
    id[x] = ++cnt;
    rev[cnt] = x;
    int ws = -1;
    for (int y: mmp[x]) {
        if (y==f) continue;
        if (ws==-1 || sz[y]>sz[ws]) ws = y;
    }
//    cout<<"ws = "<<ws<<endl;
    if (ws!=-1)
        dfs2(ws,x,tp);
    for (int y: mmp[x]) {
        if (y==f || y==ws) continue;
        dfs2(y,x,y);
    }
}

void modify(ll x,ll y) {
    while (top[x]!=top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x,y);
        update(1,1,cnt,id[top[x]],id[x]);
        x = fa[top[x]];
    }
    if (dep[x]< dep[y]) swap(x,y);
    update(1,1,cnt,id[y],id[x]);
}

ll ask(ll x,ll y) {
    ll ret = 0;
    while (top[x]!=top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x,y);
        ret += query(1,1,cnt,id[top[x]],id[x]);
        x = fa[top[x]];
    }
    if (dep[x]< dep[y]) swap(x,y);
    ret += query(1,1,cnt,id[y],id[x]);
    return ret;
}

int main() {
//    freopen("in.txt","r",stdin);

    ll n,q;
    scanf("%lld%lld",&n,&q);
    for (int i=1;i<=n;i++) {
        scanf("%lld",&a[i]);
    }
    for (int i=1;i<n;i++) {
        int x,y; scanf("%d%d",&x,&y);
        mmp[x].push_back(y);
        mmp[y].push_back(x);
    }
    dfs1(1,1,1);
    dfs2(1,1,1);
    build(1,1,cnt);
    while (q--) {
        ll op,x,y;
        scanf("%lld%lld%lld",&op,&x,&y);
        if (op==0) modify(x,y);
        else {
            ll ans = ask(x,y);
            printf("%lld\n",ans);
        }
    }
    return 0;
}