求助STL ,T了
查看原帖
求助STL ,T了
361342
┭┮﹏┭┮楼主2024/1/6 12:20
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10;
//树链剖分 + STL(multiset)
inline int read(){
	int x=0,sign=0; char s=getchar();
	while(!isdigit(s))sign|=s=='-',s=getchar();
	while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=getchar();
	return sign?-x:x;
}
int n,q;
struct made{
    int ver,nx;
}e[N<<1];
int hd[N],tot,cnt;
int fa[N],size[N],dep[N],son[N];
int dfn[N],rnk[N],top[N],a[N];
struct Tree{
    int l,r,ma,se;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define ma(x) t[x].ma
    #define se(x) t[x].se
}t[N<<2];
void pushup(int x){
    ma(x) = max(ma(x<<1),ma(x<<1|1));
    if(ma(x<<1) != ma(x<<1|1))se(x) = max(min(ma(x<<1),ma(x<<1|1)),max(se(x<<1),se(x<<1|1)));
    else se(x) = max(se(x<<1),se(x<<1|1));
}
Tree merge(Tree x,Tree y){
    Tree ans;
    ans.ma = max(x.ma,y.ma);
    if(x.ma != y.ma)ans.se = max(min(x.ma,y.ma),max(x.se,y.se));
    else ans.se = max(x.se,y.se);
    return ans;
}
void build(int x,int l,int r){
    l(x) = l,r(x) = r,ma(x) = se(x) = -1;
    if(l == r){
        ma(x) = a[rnk[l]];
        return;
    }
    int mid = l + r >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void modify(int x,int l,int z){
    if(l(x) == r(x)){
       ma(x) += z; 
       se(x) = -1;
       return;
    }
    int mid = l(x) + r(x) >> 1;
    if(l <= mid)modify(x<<1,l,z);
    else modify(x<<1|1,l,z);
    pushup(x);
}
Tree ask(int x,int l,int r){
    if(l <= l(x) && r(x) <= r)return t[x];
    int mid = l(x) + r(x) >> 1;
    if(r <= mid)return ask(x<<1,l,r);
    else if(l > mid)return ask(x<<1|1,l,r);
    else return merge(ask(x<<1,l,r),ask(x<<1|1,l,r));
}
//----------------------------
void add(int x,int y){
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}
void dfs1(int x){
    size[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(dep[y])continue;
        dep[y] = dep[x] + 1,fa[y] = x;
        dfs1(y);
        size[x] += size[y];
        if(!son[x] && size[y] > size[son[x]])son[x] = y;
    }
}
void dfs2(int x,int t){
    dfn[x] = ++cnt,top[x] = t;
    rnk[cnt] = x;
    if(!son[x])return;
    dfs2(son[x],t);
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y != fa[x] && y != son[x])dfs2(y,y);
    }
}
Tree cal(int x,int y){
    Tree ans;
    ans.ma = ans.se = -1;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        ans = merge(ans,ask(1,dfn[top[x]],dfn[x]));
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    ans = merge(ans,ask(1,dfn[x],dfn[y]));
    return ans;
}
multiset<int>s;
int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    n = read();
    for(int i = 1;i < n;i++){
        int x,y;
        x = read(),y = read();
        add(x,y),add(y,x);
    }
    for(int i = 1;i <= n;i++){
        a[i] = read();
        s.insert(a[i]);
    }
    dep[1] = 1;
    dfs1(1),dfs2(1,1);
    build(1,1,n);
    q = read();
    for(int i = 1;i <= q;i++){
        int op,x,y;
        op = read(),x = read(),y = read(); 
        if(op == 0){
            s.erase(s.find(a[x])),s.insert(a[x]+y);
            modify(1,dfn[x],y);
            a[x] += y;
        }
        else{
            Tree ans = cal(x,y);
            if(ans.se == -1){
                printf("-1\n");
                continue;
            }
            printf("%d ",ans.se);
            s.erase(s.find(ans.ma)),s.erase(s.find(ans.se));
            printf("%d\n",*(--s.lower_bound(*--s.end())));
            s.insert(ans.ma),s.insert(ans.se);
        }
    }
         
    return 0;
    
}

2024/1/6 12:20
加载中...