ABC133FColorful Tree
题意
给定一颗边有颜色和权值的树，多次询问，每次询问，首先更改颜色为x的边的权值为y，然后输出u到v的距离。
数据都是1e5量级的。
思路
我自己一开始用树链剖分的做法。
// #pragma GCC optimize(2) // #pragma GCC optimize(3) // #pragma GCC optimize(4) #include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> // #include<bits/extc++.h> // using namespace __gnu_pbds; using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /**********showtime************/ const int maxn = 1e5+9; vector<int>mp[maxn]; vector<int>col[maxn]; vector<int>wen[maxn]; struct E{ int u, v, c, d; void init(int U, int V, int C, int D) { u = U; v = V; c = C; d = D; } } edge[maxn]; int dp[maxn], son[maxn], sz[maxn], pa[maxn]; void dfs1(int u, int fa) { sz[u] = 1; pa[u] = fa; dp[u] = dp[fa] + 1; int mx = 0; for(int v : mp[u]) { if(v == fa) continue; dfs1(v, u); sz[u] += sz[v]; if(mx < sz[v]) mx = sz[v], son[u] = v; } } int id[maxn], top[maxn], tot; void dfs2(int u, int fa, int tp) { top[u] = tp; id[u] = ++tot; if(son[u]) dfs2(son[u], u, tp); for(int v : mp[u]) { if(v == fa || v == son[u]) continue; dfs2(v, u, v); } } ll ans[maxn]; ll sum[maxn<<2]; void update(int pos, int val, int le, int ri, int rt) { if(le == ri) { sum[rt] = val; return; } int mid = (le + ri) >> 1; if(pos <= mid) update(pos, val, le, mid, rt<<1); else update(pos, val, mid+1, ri, rt<<1|1); sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } ll query(int L, int R, int le, int ri, int rt) { if(le >= L && ri <= R) { return sum[rt]; } ll res = 0; int mid = (le + ri) >> 1; if(mid >= L) res += query(L, R, le, mid, rt<<1); if(mid < R) res += query(L, R, mid+1, ri, rt<<1|1); return res; } int n,m; ll solve(int u, int v) { ll res = 0; while(top[u] != top[v]) { if(dp[top[u]] > dp[top[v]]) { res += query(id[top[u]] , id[u], 1, n, 1); u = pa[top[u]]; } else { res += query(id[top[v]], id[v], 1, n, 1); v = pa[top[v]]; } } if(u != v) { if(id[u] < id[v]) res += query(id[u]+1, id[v],1, n, 1); else res += query(id[v]+1, id[u], 1, n, 1); } return res; } struct Q{ int x, y; int u,v; }q[maxn]; int main(){ scanf("%d%d", &n, &m); for(int i=1; i<n; i++) { int u, v, c, d; scanf("%d%d%d%d", &u, &v, &c, &d); edge[i].init(u, v, c, d); mp[u].pb(v); mp[v].pb(u); col[c].pb(i); } dfs1(1, 1); dfs2(1, 1, 1); for(int i=1; i<=m; i++) { scanf("%d%d%d%d", &q[i].x, &q[i].y, &q[i].u, &q[i].v); wen[q[i].x].pb(i); } for(int i=1; i<=n; i++) { if(wen[i].size() == 0 || col[i].size() == 0) continue; /// count for(int dd : col[i]) { int u = edge[dd].u; int v = edge[dd].v; if(dp[u] < dp[v]) swap(u, v); update(id[u], 1, 1, n, 1); } for(int dd: wen[i]) { ans[dd] += solve(q[dd].u, q[dd].v) * q[dd].y; } for(int dd : col[i]) { int u = edge[dd].u; int v = edge[dd].v; if(dp[u] < dp[v]) swap(u, v); update(id[u], 0, 1, n, 1); } ///sum for(int dd : col[i]) { int u = edge[dd].u; int v = edge[dd].v; if(dp[u] < dp[v]) swap(u, v); update(id[u], edge[dd].d, 1, n, 1); } for(int dd: wen[i]) { ans[dd] -= solve(q[dd].u, q[dd].v); } for(int dd : col[i]) { int u = edge[dd].u; int v = edge[dd].v; if(dp[u] < dp[v]) swap(u, v); update(id[u], 0, 1, n, 1); } } for(int i=1; i<n; i++) { int u = edge[i].u; int v = edge[i].v; if(dp[u] < dp[v]) swap(u, v); update(id[u], edge[i].d, 1, n, 1); } for(int i=1; i<=m; i++) { int u = q[i].u; int v = q[i].v; ans[i] += solve(u, v); } for(int i=1; i<=m; i++) printf("%lld ", ans[i]); return 0; }
还有树上莫队和树上差分的思路。
正在搞树上莫队的方法。搞好了。
// #pragma GCC optimize(2) // #pragma GCC optimize(3) // #pragma GCC optimize(4) #include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> // #include<bits/extc++.h> // using namespace __gnu_pbds; using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /**********showtime************/ const int maxn = 1e5+9; vector<int>mp[maxn]; struct E { int u,v; int c,d; void init(int U, int V ,int C, int D) { u = U; v = V; c = C; d = D; } } edge[maxn]; int dp[maxn]; int st[maxn ],ed[maxn], tim = 0; int fa[maxn][20]; int a[maxn*2]; void dfs(int u, int o) { dp[u] = dp[o] + 1; st[u] = ++tim; a[tim] = u; fa[u][0] = o; for(int i=1; i<20; i++) fa[u][i] = fa[fa[u][i-1]][i-1]; for(int v : mp[u]) { if(v == o) continue; dfs(v, u); } ed[u] = ++tim; a[tim] = u; } int lca(int u, int v) { if(dp[u] < dp[v]) swap(u, v); for(int i=19; i>=0; i--) { if(dp[fa[u][i]] >= dp[v]) u = fa[u][i]; } if(u == v) return u; for(int i=19; i>=0; i--) { if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; } return fa[u][0]; } int c[maxn], d[maxn]; struct Q{ // int u, v; int le, ri; int lb; int x, y; int id; } qry[maxn]; bool cmp(Q a, Q b) { if(a.lb != b.lb) return a.lb < b.lb; return a.ri < b.ri; } int ans[maxn]; int sum,colcnt[maxn],colsum[maxn],pot[maxn]; void add(int id) { if(pot[a[id]] == 0) pot[a[id]] = 1; else pot[a[id]] = 0; int col = c[a[id]]; if(pot[a[id]]) { colcnt[col] ++; colsum[col] += d[a[id]]; sum += d[a[id]]; } else { colcnt[col] --; colsum[col] -= d[a[id]]; sum -= d[a[id]]; } } int main(){ int n,m; scanf("%d%d", &n, &m); int block = 5000; for(int i=1; i<n; i++) { int u,v,c,d; scanf("%d%d%d%d", &u, &v, &c, &d); edge[i].init(u, v, c, d); mp[u].pb(v); mp[v].pb(u); } dfs(1, 1); for(int i=1; i<n; i++) { int u = edge[i].u, v = edge[i].v; if(dp[u] < dp[v]) swap(u, v); c[u] = edge[i].c; d[u] = edge[i].d; } for(int i=1; i<=m; i++) { int x, y, u, v; scanf("%d%d%d%d", &x, &y, &u, &v); qry[i].id = i; qry[i].x = x; qry[i].y = y; if(st[u] > st[v]) swap(u, v); int _lca = lca(u, v); if(_lca == u) { qry[i].le = st[u]+1; qry[i].ri = st[v]; qry[i].lb = qry[i].le / block; } else { qry[i].le = ed[u]; qry[i].ri = st[v]; qry[i].lb = qry[i].le / block; } } sort(qry+1, qry+1+m, cmp); int le = 0, ri = 0; for(int i=1; i<=m; i++) { while(le < qry[i].le) add(le), le++; while(le > qry[i].le) le--, add(le); while(ri < qry[i].ri) ri++, add(ri); while(ri > qry[i].ri) add(ri), ri--; ans[qry[i].id] = sum - colsum[qry[i].x] + colcnt[qry[i].x] * qry[i].y; } for(int i=1; i<=m; i++) printf("%d ", ans[i]); return 0; }