求助代码厌氧
查看原帖
求助代码厌氧
469345
Sherlock___Holmes楼主2022/9/30 18:34
#include <cstdio>
#define int long long
#define re register
#define get getchar()
inline int read(){
    re int x = 0;re char c = get;
    while (c < '0' || c > '9') c = get;
    while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = get;}
    return x;
}
const int n = read();
const int MAXN = 1e5 + 1;
struct edge{
    int next , to;
}a[MAXN << 1];
int head[MAXN] , w[MAXN] , wt[MAXN] , tot , cnt;
int id[MAXN] ,fa[MAXN] , dep[MAXN] , sz[MAXN] , son[MAXN] , top[MAXN];
int tree[MAXN << 2] , tag[MAXN << 2];
inline void add(re int u , re int v){
    a[++ tot].next = head[u];
    a[tot].to = v;
    head[u] = tot;
}
inline void dfs1(re int now , re int fath){
    fa[now] = fath;dep[now] = dep[fath] + 1;sz[now] = 1;
    for (re int i = head[now]; i ;i = a[i].next){
        re int y = a[i].to;
        if (y == fath) continue;
        dfs1(y , now);
        sz[now] += sz[y];
        if (sz[y] > sz[son[now]]) son[now] = y;
    }
}
inline void dfs2(re int now , re int topf){
    id[now] = ++ cnt;top[now] = topf;wt[cnt] = w[now];
    if (son[now]) dfs2(son[now] , topf);
    for (re int i = head[now]; i ;i = a[i].next){
        re int y = a[i].to;
        if (y == son[now] || y == fa[now]) continue;
        dfs2(y , y);
    }
}
inline int ls(re int p){return p << 1;}
inline int rs(re int p){return p << 1 | 1;}
inline void push_up(re int p){tree[p] = tree[ls(p)] + tree[rs(p)];}
inline void f(re int p , re int l , re int r , re int k){
    tag[p] += k;
    tree[p] += k * (r - l + 1);
}
inline void push_down(re int p , re int l , re int r){
    re int mid = l + r >> 1;
    f(ls(p) , l , mid , tag[p]);
    f(rs(p) , mid + 1 , r , tag[p]);
    tag[p] = 0;
}
inline void update(re int p , re int l , re int r , re int nl , re int nr , re int k){
    if (nl <= l && r <= nr){
        f(p , l , r , k);
        return ;
    }
    push_down(p , l , r);
    re int mid = l + r >> 1;
    if (nl <= mid) update(ls(p) , l , mid , nl , nr , k);
    if (nr > mid)  update(rs(p) , mid + 1 , r , nl , nr , k);
    push_up(p);
}
inline int query(re int p , re int l , re int r , re int nl , re int nr){
    if (nl <= l && r <= nr) return tree[p];
    re int res = 0 , mid = l + r >> 1;
    push_down(p , l , r);
    if (nl <= mid) res += query(ls(p) , l , mid , nl , nr);
    if (nr > mid)  res += query(rs(p) , mid + 1 , r , nl , nr);
    return res;
}
inline void swap(re int &x , re int &y){x ^= y ^= x ^= y;}
inline int update_tree(re int u , re int v , re int k){
    while (top[u] ^ top[v]){
        if (dep[top[u]] < dep[top[v]]) swap(u , v);
        update(1 , 1 , n , id[top[u]] , id[u] , k);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u , v);
    update(1 , 1 , n , id[u] , id[v] , k);
}
inline int query_son(re int x){return query(1 , 1 , n , id[x] , id[x] + sz[x] - 1);}
signed main(){
    for (re int i = 1;i < n;++ i){
        re int u = read() + 1 , v = read() + 1;
        add(u , v);add(v , u);
    }
    dfs1(1 , 0);dfs2(1 , 1);
    re int q = read();
    while (q --){
        re char c = get;while (c != 'A' && c != 'Q') c = get;
        re int u = read() , v , d;++ u;
        switch (c){
            case 'A':v = read() , d = read();++ v;update_tree(u , v , d);break;
            case 'Q':printf("%lld\n" , query_son(u));break;
        }
    }
    return 0;
}

该代码不加O2可以AC,但如果加了O2就会爆10个RE。。。

2022/9/30 18:34
加载中...