_zexal_ @ 2023-04-08 10:57:58
rt，本人树链剖分代码几乎等于屎山代码
by Svemit @ 2023-04-08 11:03:37
@zhong114514 link
by ColinKIA @ 2023-04-08 11:09:59
我的
#include <bits/stdc++.h>
#define int long long
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0;
T w = 1, ch = getchar();
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-')
w = -1, ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ '0'), ch = getchar();
x = x * w;
}
const int MAXN = 2e5 + 5;
int n, m, r, mod;
vector<int> G[MAXN];
int w[MAXN], wt[MAXN];
int t[MAXN * 2], lazy[MAXN * 2];
int son[MAXN], id[MAXN], cnt, fa[MAXN], dep[MAXN], size[MAXN], top[MAXN];
int res;
void add(int x, int y) { G[x].push_back(y); }
void pushdown(int p, int len) {
lazy[p * 2] += lazy[p];
lazy[p * 2 + 1] += lazy[p];
t[p * 2] += lazy[p] * (len - len / 2);
t[p * 2 + 1] += lazy[p] * (len / 2);
t[p * 2] %= mod;
t[p * 2 + 1] %= mod;
lazy[p] = 0;
}
void build(int p, int l, int r) {
if (l == r) {
t[p] = wt[l];
t[p] %= mod;
return;
}
int mid = (l + r) / 2;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
t[p] = (t[p * 2] + t[p * 2 + 1]) % mod;
}
void query(int p, int l, int r, int L, int R) {
if (L <= l && r <= R) {
res += t[p];
res %= mod;
return;
} else {
int mid = (l + r) / 2;
if (lazy[p])
pushdown(p, r - l + 1);
if (L <= mid)
query(p * 2, l, mid, L, R);
if (R > mid)
query(p * 2 + 1, mid + 1, r, L, R);
}
}
void update(int p, int l, int r, int L, int R, int k) {
if (L <= l && r <= R) {
lazy[p] += k;
t[p] += k * (r - l + 1);
return;
}
int mid = (l + r) / 2;
if (lazy[p])
pushdown(p, r - l + 1);
if (L <= mid)
update(p * 2, l, mid, L, R, k);
if (R > mid)
update(p * 2 + 1, mid + 1, r, L, R, k);
t[p] = (t[p * 2] + t[p * 2 + 1]) % mod;
}
int qrange(int x, int y) {
int ans = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])
swap(x, y);
res = 0;
query(1, 1, n, id[top[x]], id[x]);
ans += res;
ans %= mod;
x = fa[top[x]];
}
if (dep[x] > dep[y])
swap(x, y);
res = 0;
query(1, 1, n, id[x], id[y]);
ans += res;
ans %= mod;
return ans;
}
void updrange(int x, int y, int k) {
k %= mod;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])
swap(x, y);
update(1, 1, n, id[top[x]], id[x], k);
x = fa[top[x]];
}
if (dep[x] > dep[y])
swap(x, y);
update(1, 1, n, id[x], id[y], k);
}
int qson(int x) {
res = 0;
query(1, 1, n, id[x], id[x] + size[x] - 1);
return res;
}
void updson(int x, int k) { update(1, 1, n, id[x], id[x] + size[x] - 1, k); }
void dfs1(int x, int f, int deep) {
dep[x] = deep;
fa[x] = f;
size[x] = 1;
int maxson = -1;
int len = G[x].size();
for (int i = 0; i < len; i++) {
int y = G[x][i];
if (y == f)
continue;
dfs1(y, x, deep + 1);
size[x] += size[y];
if (size[y] > maxson)
son[x] = y, maxson = size[y];
}
}
void dfs2(int x, int topf) {
id[x] = ++cnt;
wt[cnt] = w[x];
top[x] = topf;
if (!son[x])
return;
dfs2(son[x], topf);
int len = G[x].size();
for (int i = 0; i < len; i++) {
int y = G[x][i];
if (y == fa[x] || y == son[x])
continue;
dfs2(y, y);
}
}
signed main() {
read(n), read(m), read(r), read(mod);
for (int i = 1; i <= n; i++) {
read(w[i]);
}
for (int i = 1; i < n; i++) {
int a, b;
read(a), read(b);
add(a, b);
add(b, a);
}
dfs1(r, 0, 1);
dfs2(r, r);
build(1, 1, n);
while (m--) {
int k, x, y, z;
read(k);
if (k == 1) {
read(x), read(y), read(z);
updrange(x, y, z);
} else if (k == 2) {
read(x), read(y);
printf("%lld\n", qrange(x, y));
} else if (k == 3) {
read(x), read(y);
updson(x, y);
} else {
read(x);
printf("%lld\n", qson(x));
}
}
return 0;
}by Sudohry @ 2023-04-08 11:18:37
放个我自己的，码风您自行评价（
//
// main.cpp
// Tree_Sep
//
// Created by n_r_q on 2022/11/21.
//
#include <iostream>
#include <cstdio>
#define N 100005
using namespace std;
//Link_Tree
int a[N<<2], ans[N<<2], tag[N<<2];
int n, m, r, p;
int ls (int x) { return x << 1 ; }
int rs (int x) { return x << 1 | 1;}
void flash (int x, int l, int r, int k) {
tag[x] += k;
ans[x] += k * (r - l + 1);
tag[x] %= p; ans[x] %= p;
return ;
}
void push_up (int x) {
ans[x] = ans[ls (x)] + ans[rs (x)];
ans[x] %= p;
return ;
}
void push_down (int x, int l, int r) {
int mid = (l + r) >> 1;
flash (ls(x), l, mid, tag[x]);
flash (rs(x), mid+1, r, tag[x]);
tag[x] = 0;
return ;
}
void build (int x, int l, int r) {
if (l == r) {
ans[x] = a[l];
return ;
}
int mid = (l + r) >> 1;
build (ls (x), l, mid);
build (rs (x), mid+1, r);
push_up (x);
return ;
}
void update (int nl, int nr, int l, int r, int pos, int k) {
if (nl <= l && r <= nr) {
flash (pos, l, r, k);
return ;
}
push_down (pos, l, r);
int mid = (l + r) >> 1;
if (nl <= mid) update (nl, nr, l, mid, ls (pos), k);
if (nr > mid) update (nl, nr, mid+1, r, rs (pos), k);
push_up (pos);
return ;
}
int query (int qx, int qy, int l, int r, int pos) {
int res = 0;
if (qx <= l && r <= qy) return ans[pos];
int mid = (l + r) >> 1;
push_down (pos, l, r);
if (qx <= mid) res += query (qx, qy, l, mid, ls (pos));
res %= p;
if (qy > mid) res += query (qx, qy, mid+1, r, rs (pos));
res %= p;
return res;
}
//Tree_Seperate
struct EDGE {
int v, n;
} edge[N<<1];
int h[N], cnt, u, v;
void add_edge (int u, int v) {
edge[++cnt] = (EDGE) {v, h[u]};
h[u] = cnt;
return ;
}
int sz[N], son[N], w[N], dep[N], fa[N], id[N], tp[N], c;
void dfs (int u) {
int maxc = -1;
sz[u] = 1;
for (int i=h[u]; i; i=edge[i].n) {
int v = edge[i].v;
if (v == fa[u]) continue ;
dep[v] = dep[u] + 1;
fa[v] = u;
dfs (v);
if (maxc < sz[v]) {
son[u] = v;
maxc = sz[v];
}
sz[u] += sz[v];
}
return ;
}
void sfd (int x, int topf) {
id[x] = ++c;
a[c] = w[x];
tp[x] = topf;
if (!son[x]) return ;
sfd (son[x], topf);
for (int i=h[x]; i; i=edge[i].n) {
int v = edge[i].v;
if (v == son[x] || v == fa[x]) continue ;
sfd (v, v);
}
return ;
}
void updpath (int x, int y, int k) {
k %= p;
while (tp[x] != tp[y]) {
if (dep[tp[x]] < dep[tp[y]]) swap (x, y);
update (id[tp[x]], id[x], 1, n, 1, k);
x = fa[tp[x]];
}
if (dep[x] > dep[y]) swap (x, y);
update (id[x], id[y], 1, n, 1, k);
return ;
}
void updsub (int x, int k) { update (id[x], id[x] + sz[x] - 1, 1, n, 1, k % p) ; }
int qrypath (int x, int y) {
int res = 0;
while (tp[x] != tp[y]) {
if (dep[tp[x]] < dep[tp[y]]) swap (x, y);
res += query(id[tp[x]], id[x], 1, n, 1);
res %= p;
x = fa[tp[x]];
}
if (dep[x] > dep[y]) swap (x, y);
res += query (id[x], id[y], 1, n, 1);
return res % p;
}
int qrysub (int x) { return query (id[x], id[x] + sz[x] - 1, 1, n, 1) ; }
int op, x, y, z;
int main() {
scanf ("%d%d%d%d", &n, &m, &r, &p);
for (int i=1; i<=n; ++i) scanf ("%d", &w[i]);
for (int i=1; i<n; ++i) {
scanf ("%d%d", &u, &v);
add_edge (u, v); add_edge (v, u);
}
dep[r] = 1;
dfs (r); sfd (r, r);
build (1, 1, n);
while (m --) {
scanf ("%d", &op);
switch (op) {
case 1:
scanf ("%d%d%d", &x, &y, &z);
updpath (x, y, z);
break;
case 2:
scanf ("%d%d", &x, &y);
printf ("%d\n", qrypath (x, y));
break;
case 3:
scanf ("%d%d", &x, &y);
updsub (x, y);
break;
case 4:
scanf ("%d", &x);
printf ("%d\n", qrysub (x));
break;
default: break;
}
}
return 0;
}
by Adchory @ 2023-04-08 11:20:54
给你一个更尸山的
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=1e5+7;
ll id[Maxn],top[Maxn],w[Maxn],sz[Maxn],son[Maxn],dep[Maxn],fa[Maxn];
// 链上编号 顶端 点权值 子树大小 重儿子编号 深度 父亲编号
ll n,m,r,p,head[Maxn],tot,cnt,wt[Maxn];
struct SegMent{
ll l,r,num,tag;
}tree[Maxn<<2];
struct edge1{
ll u,v,Next;
}Edge[Maxn<<2];
inline void add(ll u,ll v){
Edge[++tot]=(edge1){u,v,head[u]},head[u]=tot;
}
void dfs_dep(ll u,ll father){
fa[u]=father;
dep[u]=dep[father]+1;
sz[u]=1;
ll maxson=-1;
for(ll i=head[u];i;i=Edge[i].Next)
if(Edge[i].v!=fa[u]){
dfs_dep(Edge[i].v,u);
sz[u]+=sz[Edge[i].v];
if(sz[Edge[i].v]>maxson) maxson=sz[Edge[i].v],son[u]=Edge[i].v;
}
}
void dfs_new(ll x,ll topx){
id[x]=++cnt;
wt[cnt]=w[x];
top[x]=topx;
if(!son[x]) return ;
dfs_new(son[x],topx);
for(ll i=head[x];i;i=Edge[i].Next){
if(Edge[i].v==fa[x]||Edge[i].v==son[x]) continue;
dfs_new(Edge[i].v,Edge[i].v);
}
}
inline void pushup(ll node){
tree[node].num=(tree[node<<1].num+tree[node<<1|1].num)%p;
}
inline void pushdown(ll node){
tree[node<<1].num+=tree[node].tag*(tree[node<<1].r-tree[node<<1].l+1);
tree[node<<1|1].num+=tree[node].tag*(tree[node<<1|1].r-tree[node<<1|1].l+1);
tree[node<<1].tag+=tree[node].tag;
tree[node<<1|1].tag+=tree[node].tag;
tree[node<<1].num%=p,tree[node<<1|1].num%=p,tree[node<<1].tag%=p,tree[node<<1|1].tag%=p;
tree[node].tag=0;
}
inline void buildtree(ll node,ll l,ll r){
tree[node].l=l,tree[node].r=r;
if(l==r){
tree[node].num=wt[l];
tree[node].num%=p;
return ;
}
ll mid=l+r>>1;
buildtree(node<<1,l,mid);
buildtree(node<<1|1,mid+1,r);
pushup(node);
}
inline void update(ll node,ll L,ll R,ll k){
if(tree[node].l>=L&&tree[node].r<=R){
tree[node].tag+=k;
tree[node].num+=k*(tree[node].r-tree[node].l+1);
return ;
}
pushdown(node);
ll mid=tree[node].l+tree[node].r>>1;
if(L<=mid) update(node<<1,L,R,k);
if(R>mid) update(node<<1|1,L,R,k);
pushup(node);
}
inline ll query(ll node,ll L,ll R){
if(tree[node].l>=L&&tree[node].r<=R) return tree[node].num%p;
pushdown(node);
ll mid=tree[node].l+tree[node].r>>1,res=0;
if(L<=mid) res=(res+query(node<<1,L,R))%p;
if(R>mid) res=(res+query(node<<1|1,L,R))%p;
return res%p;
}
inline ll queryRange(ll x,ll y){
ll ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(1,id[top[x]],id[x]);ans%=p;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(1,id[x],id[y]);ans%=p;
return ans;
}
inline void updateRange(ll x,ll y,ll k){
k%=p;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(1,id[top[x]],id[x],k);x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(1,id[x],id[y],k);
}
inline void updateSon(ll x,ll k){
k%=p;
update(1,id[x],id[x]+sz[x]-1,k);
}
inline ll querySon(ll x){
return query(1,id[x],id[x]+sz[x]-1);
}
int main(){
scanf("%lld%lld%lld%lld",&n,&m,&r,&p);
for(ll i=1;i<=n;i++) scanf("%lld",&w[i]);
for(ll i=1,u,v;i<n;++i)
scanf("%lld%lld",&u,&v),add(u,v),add(v,u);
dfs_dep(r,0);
dfs_new(r,r);
buildtree(1,1,n);
while(m--){
ll opt,l,r,k;
scanf("%lld",&opt);
if(opt==1) scanf("%lld%lld%lld",&l,&r,&k),updateRange(l,r,k);
if(opt==2) scanf("%lld%lld",&l,&r),printf("%lld\n",queryRange(l,r)%p);
if(opt==3) scanf("%lld%lld",&l,&r),updateSon(l,r);
if(opt==4) scanf("%lld",&l),printf("%lld\n",querySon(l)%p);
}
return 0;
}by Poncirus @ 2023-04-08 11:23:33
该问题是无意义的，因为大多数人都觉得自己的码风全世界第一优美，其他人的码风都像粪。
by Iictiw @ 2023-04-08 11:32:08
link
by 冰糖鸽子 @ 2023-04-08 11:40:12
大多数人都觉得自己的码风全世界第一优美。
by Raisetsu41 @ 2023-04-08 11:43:40
https://www.luogu.com.cn/paste/czf7adwv
by billtun @ 2023-12-31 11:43:43
不自量力的举荐一下
#include <bits/stdc++.h>
#define ll long long
#define Maxn 100005
using namespace std;
ll read() {
ll ret = 0, sgn = 0, ch = getchar();
while (!isdigit(ch)) {
sgn |= (ch == '-'), ch = getchar();
}
while (isdigit(ch)) {
ret = ret * 10 + ch - '0', ch = getchar();
}
return !sgn ? ret : -ret;
}
ll n, m, rt, MOD, w[Maxn], a, b;
ll fa[Maxn], siz[Maxn], dep[Maxn], son[Maxn];
ll dfn[Maxn], rnk[Maxn], dfncnt = 0, top[Maxn];
vector<ll> v[Maxn];
ll opt, x, y, z;
void dfs1(ll x) {
son[x] = -1, siz[x] = 1;
for (ll i = 0; i < (ll)v[x].size(); i++) {
ll tmp = v[x][i];
if (!dep[tmp]) {
dep[tmp] = dep[x] + 1, fa[tmp] = x;
dfs1(tmp), siz[x] += siz[tmp];
son[x] = ((son[x] == -1 || siz[son[x]] < siz[tmp]) ? tmp : son[x]);
}
}
}
void dfs2(ll x, ll Top) {
top[x] = Top;
dfn[x] = ++dfncnt, rnk[dfn[x]] = x;
if (son[x] == -1) {
return ;
}
dfs2(son[x], Top);
for (ll i = 0; i < (ll)v[x].size(); i++) {
ll tmp = v[x][i];
if (tmp != son[x] && tmp != fa[x]) {
dfs2(tmp, tmp);
}
}
}
struct SEG_tree {
#define lid (id<<1)
#define rid (id<<1|1)
struct seg_tree {
ll l, r, lazy, sum;
} tr[Maxn << 2];
void build(ll id, ll l, ll r) {
tr[id].l = l, tr[id].r = r;
if (l == r) {
tr[id].lazy = 0, tr[id].sum = w[rnk[l]] % MOD;
return ;
}
ll mid = (l + r) >> 1;
build(lid, l, mid), build(rid, mid + 1, r);
tr[id].lazy = 0, tr[id].sum = (tr[lid].sum + tr[rid].sum) % MOD;
}
void pushdown(ll id) {
if (tr[id].l != tr[id].r && tr[id].lazy) {
tr[lid].sum = (tr[lid].sum + (tr[lid].r - tr[lid].l + 1) * tr[id].lazy) % MOD;
tr[rid].sum = (tr[rid].sum + (tr[rid].r - tr[rid].l + 1) * tr[id].lazy) % MOD;
tr[lid].lazy += tr[id].lazy % MOD, tr[rid].lazy += tr[id].lazy % MOD;
tr[id].lazy = 0;
}
}
void add(ll id, ll l, ll r, ll val) {
pushdown(id);
if (tr[id].l == l && tr[id].r == r) {
tr[id].sum = (tr[id].sum + (tr[id].r - tr[id].l + 1) * val) % MOD, tr[id].lazy = (tr[id].lazy + val) % MOD;
return ;
}
ll mid = (tr[id].l + tr[id].r) >> 1;
if (r <= mid) {
add(lid, l, r, val);
} else if (l > mid) {
add(rid, l, r, val);
} else {
add(lid, l, mid, val), add(rid, mid + 1, r, val);
}
tr[id].sum = (tr[lid].sum + tr[rid].sum) % MOD;
}
ll query(ll id, ll l, ll r) {
pushdown(id);
if (tr[id].l == l && tr[id].r == r) {
return tr[id].sum % MOD;
}
ll mid = (tr[id].l + tr[id].r) >> 1;
if (r <= mid) {
return query(lid, l, r) % MOD;
} else if (l > mid) {
return query(rid, l, r) % MOD;
} else {
return (query(lid, l, mid) % MOD + query(rid, mid + 1, r) % MOD) % MOD;
}
}
} sg;
void addl(ll x, ll y, ll Val) {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
x ^= y, y ^= x, x ^= y;
}
sg.add(1, dfn[top[y]], dfn[y], Val);
y = fa[top[y]];
}
if (dep[x] > dep[y]) {
x ^= y, y ^= x, x ^= y;
}
sg.add(1, dfn[x], dfn[y], Val);
}
ll Query(ll x, ll y) {
ll res = 0;
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
x ^= y, y ^= x, x ^= y;
}
res = (res + sg.query(1, dfn[top[y]], dfn[y])) % MOD;
y = fa[top[y]];
}
if (dep[x] > dep[y]) {
x ^= y, y ^= x, x ^= y;
}
res = (res + sg.query(1, dfn[x], dfn[y])) % MOD;
return res;
}
int main() {
n = read(), m = read(), rt = read(), MOD = read();
for (ll i = 1; i <= n; i++) {
w[i] = read(), w[i] %= MOD;
}
for (ll i = 1; i < n; i++) {
a = read(), b = read();
v[a].push_back(b);
v[b].push_back(a);
}
dep[rt] = 1, fa[rt] = 0;
dfs1(rt), dfs2(rt, rt);
sg.build(1, 1, n);
for (ll i = 1; i <= m; i++) {
opt = read();
if (opt == 1) {
x = read(), y = read(), z = read();
addl(x, y, z);
} else if (opt == 2) {
x = read(), y = read();
printf("%lld\n", Query(x, y));
} else if (opt == 3) {
x = read(), z = read();
sg.add(1, dfn[x], dfn[x] + siz[x] - 1, z);
} else if (opt == 4) {
x = read();
printf("%lld\n", sg.query(1, dfn[x], dfn[x] + siz[x] - 1) % MOD);
}
}
return 0;
}