2 条题解
-
0
#include <bits/stdc++.h> #define block(i) ((i + b - 1) / b) #define N 100034 #define M 100034 #define Q 100034 using namespace std; typedef long long ll; typedef vector <int> vec; struct req{ int x, y, z, id; req (int x0 = 0, int y0 = 0, int z0 = 0, int id0 = 0): x(x0), y(y0), z(z0), id(id0) {} req *read(int id0 = 0, int z0 = 0){ scanf("%d%d", &x, &y); id = id0; z = z0; return this;} }; // normal int n, m, q, b; int i, j, u0, v0; int c0, c1, ch; int v[M], w[N], c[N], la[N]; vec g[N]; // for lca and tree int cunt, dep[N], ord[N << 3], ordF[N], ordL[N]; // ordF[](ordL[]) is the first(last) timestamp a vertex appear int f[20][N << 3]; // for query or modui int lp, rp, tp; int vis[N], cnt[M]; // vis[] for if point is visited, cnt[] for candy is eaten ll cur, ans[N]; req mod[Q], qur[Q]; bool cmp(const req &x, const req &y){ int bxx = block(x.x), byx = block(y.x), bxy = block(x.y), byy = block(y.y); return bxx < byx || bxx == byx && (bxy < byy || bxy == byy && x.z < y.z); } inline int dmin(int x, int y){return dep[x] < dep[y] ? x : y;} void dfs(int node, int depth){ bool ok = false; dep[node] = depth; for(vec :: iterator it = g[node].begin(); it != g[node].end(); ++it) if(dep[*it] < 0){ ok = true; if(ordF[node] < 0) ordF[node] = cunt; ord[cunt++] = node; dfs(*it, depth + 1); ord[cunt++] = node; } if(!ok){ordF[node] = cunt; ord[cunt++] = node; ord[cunt++] = node;} ordL[node] = cunt - 1; } inline int LCA(int x, int y){ int L = min(ordF[x], ordF[y]), R = (ordF[x] ^ ordF[y] ^ L) + 1, D = R - L, c = (int)floor(log2(D) + 1e-6); return dmin(f[c][L], f[c][R - (1 << c)]); } inline void spit(int x){cur -= (ll)v[x] * w[cnt[x]--];} inline void eat(int x){cur += (ll)v[x] * w[++cnt[x]];} inline void deal(int pos){(vis[pos] ^= 1) ? eat(c[pos]) : spit(c[pos]);} inline void modify(int pos, int v){if(vis[pos]){spit(c[pos]); eat(c[pos] = v);} else c[pos] = v;} int main(){ // init scanf("%d%d%d", &n, &m, &q); for(i = 1; i <= m; i++) scanf("%d", v + i); for(i = 1; i <= n; i++) scanf("%d", w + i); for(i = 1; i < n; i++){ scanf("%d%d", &u0, &v0); g[u0].push_back(v0); g[v0].push_back(u0); } for(i = 1; i <= n; i++){scanf("%d", c + i); la[i] = c[i];} // get lca memset(dep, -1, sizeof dep); memset(ordF, -1, sizeof ordF); memset(ordL, -1, sizeof ordL); dfs(1, cunt = 0); memcpy(f[0], ord, cunt << 2); for(j = 0; 1 << j + 1 <= cunt; j++) for(i = 0; i <= cunt - (1 << j + 1); i++) f[j + 1][i] = dmin(f[j][i], f[j][i + (1 << j)]); b = (int)pow(cunt, 0.682936); // modui memset(vis, 0, sizeof vis); memset(cnt, 0, sizeof cnt); for(c0 = c1 = i = 0; i < q; i++) if(scanf("%d", &ch), ch){ qur[c1].read(++c1, c0); if(qur[c1].x[ordF] > qur[c1].y[ordF]) swap(qur[c1].x, qur[c1].y); qur[c1].x = (qur[c1].x[ordL] < qur[c1].y[ordF] ? qur[c1].x[ordL] : qur[c1].x[ordF]); qur[c1].y = qur[c1].y[ordF]; }else{ mod[c0].read(++c0); mod[c0].z = la[mod[c0].x]; la[mod[c0].x] = mod[c0].y; } sort(qur + 1, qur + (c1 + 1), cmp); tp = cur = lp = 0; rp = -1; for(i = 1; i <= c1; i++){ while(tp < qur[i].z) modify(mod[tp].x, mod[++tp].y); while(tp > qur[i].z) modify(mod[tp--].x, mod[tp].z); while(lp < qur[i].x) deal(ord[lp++]); while(lp > qur[i].x) deal(ord[--lp]); while(rp < qur[i].y) deal(ord[++rp]); while(rp > qur[i].y) deal(ord[rp--]); u0 = LCA(ord[lp], ord[rp]); v0 = (u0 == ord[lp] || u0 == ord[rp]); if(!v0) deal(u0); ans[qur[i].id] = cur; if(!v0) deal(u0); } for(i = 1; i <= c1; i++) printf("%lld\n", ans[i]); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:07:47
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=2e5+10; vector<int>G[N]; int fa[N], son[N], siz[N], dep[N], top[N]; int tsp; int in[N], out[N], a[N]; void dfs1(int x, int ff) { siz[x]=1; dep[x]=dep[ff]+1; fa[x]=ff; son[x]=0; for(auto y:G[x]) if(y!=ff) { dfs1(y, x); siz[x]+=siz[y]; if(siz[son[x]] < siz[y]) son[x]=y; } } void dfs2(int x, int tp) { in[x]=++tsp; a[tsp]=x; // 括号序 top[x]=tp; if(son[x]) dfs2(son[x], tp); for(auto y:G[x]) if(y!=fa[x] && y!=son[x]) dfs2(y, y); out[x]=++tsp; a[tsp]=x; } int LCA(int x, int y) { while(top[x]!=top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x, y); x=fa[top[x]]; } return dep[x] < dep[y]?x:y; } int n, m, k, B, V[N], W[N], C[N]; int vis[N], cnt[N]; LL ans[N], sum; struct Qnode{int l, r, lca, t, id;}q[N];int mq; bool cmp(const Qnode &n1, const Qnode &n2) { if(n1.l/B != n2.l/B) return n1.l < n2.l; if(n1.r/B != n2.r/B) return n1.r < n2.r; return n1.t < n2.t; } struct Rnode{int p, c;}R[N];int mr; void add(int x) { vis[x]^=1; if(vis[x]) sum += 1LL * W[++cnt[C[x]]] * V[C[x]]; else sum -= 1LL * W[cnt[C[x]]--] * V[C[x]]; } int main() { scanf("%d%d%d", &n, &m, &k); for(int i=1; i<=m; ++i) scanf("%d", &V[i]); for(int i=1; i<=n; ++i) scanf("%d", &W[i]); for(int i=1, x, y; i < n; i++) { scanf("%d%d", &x, &y); G[x].push_back(y); G[y].push_back(x); } dfs1(1, 0); dfs2(1, 1); for(int i=1; i<=n; i++) scanf("%d", &C[i]); // 糖果类型 mq=mr=0; for(int i=1, op, x, y; i <= k; i++) { scanf("%d%d%d", &op, &x, &y); if(op==1) { ++mq; if(in[x] > in[y]) swap(x, y); // 先x后y int lca = LCA(x, y); if(lca == x) q[mq] = {in[x], in[y], 0, mr, mq}; // 直链情况 else q[mq] = {out[x], in[y], lca, mr, mq}; // 折链情况 } else R[++mr] = {x, y}; // 修改值 } // 树上带修莫队 B = pow(2*n, 0.66); sort(q+1, q+mq+1, cmp); for(int i=1, l=1, r=0, t=0; i <= mq; i++) { while(l > q[i].l) add(a[--l]); while(l < q[i].l) add(a[l++]); while(r > q[i].r) add(a[r--]); while(r < q[i].r) add(a[++r]); while(t < q[i].t) { // 时间戳变大则替换 ++t; if(vis[R[t].p]) { add(R[t].p); swap(C[R[t].p], R[t].c); // 换成修改值 add(R[t].p); } else swap(C[R[t].p], R[t].c); } while(t > q[i].t) { // 时间戳变小则还原 if(vis[R[t].p]) { add(R[t].p); swap(C[R[t].p], R[t].c); // 还原修改值? add(R[t].p); } else swap(C[R[t].p], R[t].c); t--; } ans[q[i].id] = sum; if(q[i].lca) ans[q[i].id] += 1LL * W[cnt[C[q[i].lca]] + 1] * V[C[q[i].lca]]; // 补上lca的 } for(int i=1; i<=mq; ++i) printf("%lld\n", ans[i]); return 0; }
- 1
