把register删了O2也能过
by CH_mengxiang @ 2022-09-30 18:38:54
没有足够把握,小优化尽量不加
by CH_mengxiang @ 2022-09-30 18:39:17
应该是数组越界
by panyanppyy @ 2022-09-30 18:55:32
@[Sherlock___Holmes](/user/469345) 你把 $n$ 开大一点试试
by panyanppyy @ 2022-09-30 18:57:15
@[panyanppyy](/user/262322) 那也不应该全RE吧
by Sherlock___Holmes @ 2022-09-30 19:01:29
@[PRC_Dreamwastaken](/user/190485) 可是为什么我删了以后还是全RE?
by Sherlock___Holmes @ 2022-09-30 19:05:23
@[Sherlock___Holmes](/user/469345) `update_tree` 函数没有返回值,是未定义行为,可能造成 RE。
by Dr_Gilbert @ 2022-09-30 19:15:27
```cpp
#include <cstdio>
#define int long long
#define get getchar()
inline int read(){
int x = 0;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(int u , int v){
a[++ tot].next = head[u];
a[tot].to = v;
head[u] = tot;
}
inline void dfs1(int now , int fath){
fa[now] = fath;dep[now] = dep[fath] + 1;sz[now] = 1;
for (int i = head[now]; i ;i = a[i].next){
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(int now , int topf){
id[now] = ++ cnt;top[now] = topf;wt[cnt] = w[now];
if (son[now]) dfs2(son[now] , topf);
for (int i = head[now]; i ;i = a[i].next){
int y = a[i].to;
if (y == son[now] || y == fa[now]) continue;
dfs2(y , y);
}
}
inline int ls(int p){return p << 1;}
inline int rs(int p){return p << 1 | 1;}
inline void push_up(int p){tree[p] = tree[ls(p)] + tree[rs(p)];}
inline void f(int p , int l , int r , int k){
tag[p] += k;
tree[p] += k * (r - l + 1);
}
inline void push_down(int p , int l , int r){
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(int p , int l , int r , int nl , int nr , int k){
if (nl <= l && r <= nr){
f(p , l , r , k);
return ;
}
push_down(p , l , r);
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(int p , int l , int r , int nl , int nr){
if (nl <= l && r <= nr) return tree[p];
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(int &x , int &y){x ^= y ^= x ^= y;}
inline int update_tree(int u , int v , 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(int x){return query(1 , 1 , n , id[x] , id[x] + sz[x] - 1);}
signed main(){
for (int i = 1;i < n;++ i){
int u = read() + 1 , v = read() + 1;
add(u , v);add(v , u);
}
dfs1(1 , 0);dfs2(1 , 1);
int q = read();
while (q --){
char c = get;while (c != 'A' && c != 'Q') c = get;
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;
}
```
满分
by CH_mengxiang @ 2022-09-30 19:17:09
@[Sherlock___Holmes](/user/469345)
by CH_mengxiang @ 2022-09-30 19:18:14
@[PRC_Dreamwastaken](/user/190485) 你可以看我记录,我又RE了,直接复制的你的
by Sherlock___Holmes @ 2022-09-30 19:22:51