imsbNR @ 2024-08-22 14:19:37
马蜂能懂，玄关求条，样例第一问过不了。
听说内容和标题互换会多来点人
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
vector <ll> G[N];
ll n, m, r, p, x, y, z, cnt, op, u, v, k;
ll fa[N], dep[N], sz[N], son[N], top[N], val[N], ide[N], nw[N], t[N << 2], la[N << 2];
void dfs1(ll u, ll f)
{
dep[u] = dep[f] + 1;
fa[u] = f;
sz[u] = 1;
for (auto g : G[u])
if (g != f)
{
dfs1(g, u);
sz[u] += sz[g];
if (sz[g] > sz[son[u]])
son[u] = g;
}
return;
}
void dfs2(ll u, ll t)
{
top[u] = t;
ide[u] = ++cnt;
nw[cnt] = val[u];
if (!son[u])
return;
dfs2(son[u], t);
for (auto g : G[u])
if (g != son[u] and g != fa[u])
dfs2(g, g);
return;
}
ll ls(ll i) {return i << 1;}
ll rs(ll i) {return i << 1 | 1;}
void build(ll l, ll r, ll i)
{
if (l == r)
{
t[i] = nw[l];
return;
}
ll mid = (l + r) >> 1;
build(l, mid, ls(i));
build(mid + 1, r, rs(i));
t[i] = (t[ls(i)] + t[rs(i)]) % p;
return;
}
void spread(ll l, ll r, ll i)
{
if (!la[i])
return;
ll mid = (l + r) >> 1;
la[ls(i)] += la[i] % p;
la[ls(i)] %= p;
la[rs(i)] += la[i] % p;
la[rs(i)] %= p;
la[i] = 0;
t[ls(i)] += (mid - l + 1) * la[ls(i)] % p;
t[ls(i)] %= p;
t[rs(i)] += (r - mid) * la[rs(i)] % p;
t[rs(i)] %= p;
t[i] = (t[ls(i)] + t[rs(i)]) % p;
return;
}
void update(ll l, ll r, ll i, ll x, ll y, ll v)
{
spread(l, r, i);
if (x <= l and r <= y)
{
la[i] += v;
la[i] %= p;
t[i] += v * (r - l + 1) % p;
t[i] %= p;
return;
}
spread(l, r, i);
ll mid = (l + r) >> 1;
if (x <= mid)
update(l, mid, ls(i), x, y, v);
if (mid < y)
update(mid + 1, r, rs(i), x, y, v);
t[i] = (t[ls(i)] + t[rs(i)]) % p;
return;
}
ll query(ll l, ll r, ll i, ll x, ll y)
{
if (x <= l and r <= y)
return t[i];
ll mid = (l + r) >> 1, ans = 0;
if (x <= mid)
ans += query(l, mid, ls(i), x, y);
ans %= p;
if (mid < y)
ans += query(mid + 1, r, rs(i), x, y);
ans %= p;
return ans;
}
void lca_update(ll u, ll v, ll k)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
update(1, n, 1, ide[top[u]], ide[u], k);
u = fa[top[u]];
}
update(1, n, 1, ide[top[u]], ide[u], k);
return;
}
ll lca_query(ll u, ll v)
{
ll ans = 0;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
ans = (ans + query(1, n, 1, ide[top[u]], ide[u])) % p;
u = fa[top[u]];
}
if (dep[u] < dep[v])
swap(u, v);
ans = (ans + query(1, n, 1, ide[top[u]], ide[u])) % p;
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> r >> p;
for (int i = 1; i <= n; i++)
cin >> val[i];
for (int i = 1; i < n; i++)
{
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs1(r, 0);
dfs2(r, 0);
build(1, n, 1);
while (m--)
{
cin >> op;
if (op == 1)
{
cin >> u >> v >> k;
lca_update(u, v, k);
}
else if (op == 2)
{
cin >> u >> v;
cout << lca_query(u, v) << '\n';
}
else if (op == 3)
{
cin >> u >> k;
update(1, n, 1, ide[u], ide[u] + sz[u] - 1, k);
}
else if (op == 4)
{
cin >> u;
cout << query(1, n, 1, ide[u], ide[u] + sz[u] - 1) << '\n';
}
}
return 0;
}by Guchenxi0971 @ 2024-08-22 14:37:55
@imsbNR
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
vector <ll> G[N];
ll n, m, r, p, x, y, z, cnt, op, u, v, k;
ll fa[N], dep[N], sz[N], son[N], top[N], val[N], ide[N], nw[N], t[N << 2], la[N << 2];
void dfs1(ll u, ll f)
{
dep[u] = dep[f] + 1;
fa[u] = f;
sz[u] = 1;
for (auto g : G[u])
if (g != f)
{
dfs1(g, u);
sz[u] += sz[g];
if (sz[g] > sz[son[u]])
son[u] = g;
}
return;
}
void dfs2(ll u, ll t)
{
top[u] = t;
ide[u] = ++cnt;
nw[cnt] = val[u];
if (!son[u])
return;
dfs2(son[u], t);
for (auto g : G[u])
if (g != son[u] and g != fa[u])
dfs2(g, g);
return;
}
ll ls(ll i) {return i << 1;}
ll rs(ll i) {return i << 1 | 1;}
void build(ll l, ll r, ll i)
{
if (l == r)
{
t[i] = nw[l];
return;
}
ll mid = (l + r) >> 1;
build(l, mid, ls(i));
build(mid + 1, r, rs(i));
t[i] = (t[ls(i)] + t[rs(i)]) % p;
return;
}
void spread(ll l, ll r, ll i)
{
if (!la[i])
return;
ll mid = (l + r) >> 1;
la[ls(i)] += la[i] % p;
la[ls(i)] %= p;
la[rs(i)] += la[i] % p;
la[rs(i)] %= p;
t[ls(i)] += (mid - l + 1) * la[i] % p;
t[ls(i)] %= p;
t[rs(i)] += (r - mid) * la[i] % p;
t[rs(i)] %= p;
la[i] = 0;
// t[i] = (t[ls(i)] + t[rs(i)]) % p;
return;
}
void update(ll l, ll r, ll i, ll x, ll y, ll v)
{
if (x <= l and r <= y)
{
la[i] += v;
la[i] %= p;
t[i] += v * (r - l + 1) % p;
t[i] %= p;
return;
}
spread(l, r, i);
ll mid = (l + r) >> 1;
if (x <= mid)
update(l, mid, ls(i), x, y, v);
if (mid < y)
update(mid + 1, r, rs(i), x, y, v);
t[i] = (t[ls(i)] + t[rs(i)]) % p;
return;
}
ll query(ll l, ll r, ll i, ll x, ll y)
{
if (x <= l and r <= y)
return t[i];
spread(l, r, i);
ll mid = (l + r) >> 1, ans = 0;
if (x <= mid)
ans += query(l, mid, ls(i), x, y);
ans %= p;
if (mid < y)
ans += query(mid + 1, r, rs(i), x, y);
ans %= p;
return ans;
}
void lca_update(ll u, ll v, ll k)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
update(1, n, 1, ide[top[u]], ide[u], k);
u = fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
update(1, n, 1, ide[u], ide[v], k);
return;
}
ll lca_query(ll u, ll v)
{
ll ans = 0;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
ans = (ans + query(1, n, 1, ide[top[u]], ide[u])) % p;
u = fa[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
ans = (ans + query(1, n, 1, ide[u], ide[v])) % p;
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> r >> p;
for (int i = 1; i <= n; i++){
cin >> val[i];val[i]%=p;}
for (int i = 1; i < n; i++)
{
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs1(r, 0);
dfs2(r, r);
build(1, n, 1);
while (m--)
{
cin >> op;
if (op == 1)
{
cin >> u >> v >> k;
lca_update(u, v, k);
}
else if (op == 2)
{
cin >> u >> v;
cout << lca_query(u, v) << '\n';
}
else if (op == 3)
{
cin >> u >> k;
update(1, n, 1, ide[u], ide[u] + sz[u] - 1, k);
}
else if (op == 4)
{
cin >> u;
cout << query(1, n, 1, ide[u], ide[u] + sz[u] - 1) << '\n';
}
}
return 0;
}
改了在线段树的spread以及：
void lca_update(ll u, ll v, ll k)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
update(1, n, 1, ide[top[u]], ide[u], k);
u = fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
update(1, n, 1, ide[u], ide[v], k);
return;
}
ll lca_query(ll u, ll v)
{
ll ans = 0;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
ans = (ans + query(1, n, 1, ide[top[u]], ide[u])) % p;
u = fa[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
ans = (ans + query(1, n, 1, ide[u], ide[v])) % p;
return ans;
}这两个函数，还有线段树query中忘了spread
by imsbNR @ 2024-08-22 14:39:32
@Guchenxi0971 谢谢你已关
by Guchenxi0971 @ 2024-08-22 14:40:15
@imsbNR 还有输入的val要取模，不然wa on #11
by imsbNR @ 2024-08-22 14:43:13
@Guchenxi0971 为什么要删掉spread的 t[i] = (t[ls(i)] + t[rs(i)]) % p;
by Guchenxi0971 @ 2024-08-22 14:45:07
@imsbNR 其实这个没必要，因为你到了i这个节点是更新过它的t了的才会下传tag。
by imsbNR @ 2024-08-22 15:45:57
@Guchenxi0971 19pts，死了
by Guchenxi0971 @ 2024-08-22 16:23:22
@imsbNR 主要还是spread的问题，如果改成我的习惯写法是
void spread(ll l, ll r, ll i)
{
if (!la[i])
return;
ll mid = (l + r) >> 1;
la[ls(i)] += la[i] % p;
la[ls(i)] %= p;
la[rs(i)] += la[i] % p;
la[rs(i)] %= p;
t[ls(i)] += (mid - l + 1) * la[i] % p;
t[ls(i)] %= p;
t[rs(i)] += (r - mid) * la[i] % p;
t[rs(i)] %= p;
la[i] = 0;
// t[i] = (t[ls(i)] + t[rs(i)]) % p;
return;
}by Guchenxi0971 @ 2024-08-22 16:30:58
@imsbNR 因为原来i的儿子的la在加入新的tag之前都是已经处理过的，即贡献已经在t上了，当加入新的tag是只需要算新tag的贡献
by imsbNR @ 2024-08-22 16:36:35
@Guchenxi0971 AC了，谢谢 dalao