《萌新袜子》
《刚学 CSP》
by szx20100828 @ 2023-09-28 21:52:48
@[szx20100828](/user/678019) 确实，今年第一次进复赛\
话说我这是哪里错了 /kk
by Snowy_Fujisaki @ 2023-09-28 21:54:08
尝试多开点空间？总有一种空间小了的感觉
by liaiyang @ 2023-09-28 21:58:58
忘标记清零，清零后 46pts：
```
#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)
//#define int ll
#define itn int
#define umap unordered_map
#define uset unordered_set
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
int dep[maxn], fa[maxn], top[maxn], hson[maxn], siz[maxn], dfn[maxn], rnk[maxn];
int tot;
int n, m, root, mod;
vector<int> G[maxn];
int d[maxn * 4], b[maxn * 4];
int num[maxn];
inline void dfs1(int u){
hson[u] = -1;
siz[u] = 1;
for(auto v : G[u]){
if(!dep[v]){
dep[v] = dep[u] + 1, fa[v] = u;
dfs1(v);
siz[u] += siz[v];
if(hson[u] == -1 || siz[v] > siz[hson[u]]) hson[u] = v;
}
}
}
inline void dfs2(int u, int f){
top[u] = f;
dfn[u] = ++tot;
rnk[tot] = u;
if(hson[u] == -1)
return;
dfs2(hson[u], f);
for(auto v : G[u])
if(v != hson[u] && v != fa[u])
dfs2(v, v);
}
inline void build(int l, int r, int p){
if(l == r){
d[p] = num[rnk[l]] % mod;
return;
}
int mid = l + ((r - l) >> 1);
build(l, mid, p << 1),
build(mid + 1, r, (p << 1) | 1);
d[p] = (d[p << 1] + d[(p << 1) | 1]) % mod;
}
inline void pd(int s, int t, int p){
int l = (p << 1), r = (p << 1) | 1, mid = (s + t) >> 1;
if(b[p]){
b[l] += b[p];
b[r] += b[p];
d[l] = (d[l] + b[p] * (mid - s + 1)) % mod;
d[r] = (d[r] + b[p] * (t - mid)) % mod;
}
b[p] = 0;
}
inline void update(int l,int r,int c,int s,int t,int p){
if(l <= s && t <= r){
d[p] += (t - s + 1) * c,b[p] += c;
return;
}
int m = s + ((t - s) >> 1);
pd(s, t, p);
if(l <= m) update(l, r, c, s, m, p << 1);
if(r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
d[p] = (d[p << 1] + d[(p << 1) | 1]) % mod;
}
inline int getsum(int l,int r,int s,int t,int p){
if(l <= s && t <= r)
return d[p] % mod;
int m = s + ((t - s) >> 1);
int sum = 0;
pd(s, t, p);
if(l <= m) sum = (sum + getsum(l, r, s, m, p << 1)) % mod;
if(r > m) sum = (sum + getsum(l, r, m + 1, t, (p << 1) | 1)) % mod;
return sum;
}
inline void upd(int s, int t, int c){
c %= mod;
while(top[s] != top[t]){
if(dep[top[s]] < dep[top[t]])
swap(s, t);
update(dfn[top[s]], dfn[s], c, 1, n, 1);
s = fa[top[s]];
}
if(dep[s] > dep[t])
swap(s, t);
update(dfn[s], dfn[t], c, 1, n, 1);
}
inline int get(int s, int t){
int ret = 0;
while(top[s] != top[t]){
if(dep[top[s]] < dep[top[t]])
swap(s, t);
ret = (ret + getsum(dfn[top[s]], dfn[s], 1, n, 1)) % mod;
s = fa[top[s]];
}
if(dep[s] > dep[t])
swap(s, t);
ret = (ret + getsum(dfn[s], dfn[t], 1, n, 1)) % mod;
return ret;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> root >> mod;
F(i, 1, n)
cin >> num[i];
F(i, 1, n - 1){
int u, v;
cin >> u >> v;
G[u].pb(v), G[v].pb(u);
}
dfs1(root);
dfs2(root, 0);
build(1, n, 1);
while(m--){
int op;
cin >> op;
if(op == 1){
int x, y, z;
cin >> x >> y >> z;
upd(x, y, z);
}
else if(op == 2){
int x, y;
cin >> x >> y;
cout << get(x, y) << '\n';
}
else if(op == 3){
int x, y;
cin >> x >> y;
update(dfn[x], dfn[x] + siz[x] - 1, y, 1, n, 1);
}
else if(op == 4){
int x;
cin >> x;
cout << getsum(dfn[x], dfn[x] + siz[x] - 1, 1, n, 1) << '\n';
}
}
return 0;
}
```
by Snowy_Fujisaki @ 2023-09-28 22:04:16
@[liaiyang](/user/783170) 可是MLE 3个
by Snowy_Fujisaki @ 2023-09-28 22:04:45
@[OIer1030](/user/759710) 空间开小了啥牛马东西都能出来说实话
by liaiyang @ 2023-09-28 22:08:28
@[liaiyang](/user/783170) 8 倍空间都没用 /kk
by Snowy_Fujisaki @ 2023-09-28 22:11:13
@[liaiyang](/user/783170) 好了，树剖dfs1问题，thx
by Snowy_Fujisaki @ 2023-09-28 22:22:06
@[OIer1030](/user/759710) 您这个 $dep[root]$ 是不是就是$0$，而在之后 $dep[root]$ 又会变成 $2$
by zzy0618 @ 2023-09-28 23:00:05
使用有意义且描述明确的标题
在邮件列表、新闻群组或论坛中，大约 50 字以内的标题是抓住资深专家注意力的好机会。别用喋喋不休的「帮帮忙」、「跪求」、「急」、「萌新刚学 OI xxx s」、「萌新妹子求助」（更别说 「救命啊！！！！」这样让人反感的话，用这种标题会被条件反射式地忽略）来浪费这个机会。不要妄想用你的痛苦程度来打动我们，而应该是在这点空间中使用极简单扼要的描述方式来提出问题。
——《洛谷新用户必读》—《提问的智慧》
by LoadingSpace @ 2023-09-29 19:53:32