Gym102059A Coloring Roads

---

題意：\(n\)點的樹，一開始每條邊都沒有顏色，有\(Q\)個操作，每次將從\(u\)到\(1\)路徑上的所有邊全部染色為顏色\(c\)，之后詢問整棵樹上，出現了\(m\)次的顏色有多少種。數據范圍均是\(200000\)。

做法：詢問的東西十分奇怪沒有辦法下手，于是注意到每次的修改都是染色，而且染色的路徑也很特殊。于是我們猜測在這種操作方式下，一條路徑上連續相同的顏色段數有一個比較優秀的期望值。先考慮如何在一個序列上，進行賦值操作，我們想到了\(ODT\)，在修改的同時維護每種顏色出現的次數和每種次數對應的顏色的種類數。對于每次詢問的路徑，通過樹剖把問題轉化到為序列上處理。。。

#include <bits/stdc++.h> #define rep(i,a,b) for(int i = a; i <= b; ++i) #define pb push_back typedef long long ll; const int N = 1 << 18 | 5; template<class T> inline void read(T &x) {x = 0; char c = getchar(); T f = 1;while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}while(isdigit(c)) {x = x * 10 + c - '0'; c = getchar();}x *= f; } using namespace std; int n, C, Q; vector<int> G[N]; int id[N], dfn, top[N], fa[N], sz[N], son[N]; void dfs1(int u, int pre) {sz[u] = 1; fa[u] = pre;int weight = 0;for(int v: G[u]) if(v != pre) {dfs1(v, u);sz[u] += sz[v];if(weight < sz[v]) weight = sz[v], son[u] = v;} } void dfs2(int u, int tp) {top[u] = tp; id[u] = ++dfn;if(son[u]) dfs2(son[u],tp);for(int v: G[u]) if(v != fa[u] && v != son[u]) {dfs2(v,v);} } int ans[N], col[N]; struct Seg{int l, r, c;bool operator < (const Seg &a) const {return r < a.r;} }; set< Seg > S; void split(int p) {auto s = S.lower_bound({p,p});if(s == S.end() || (s->l) > p || p == s->r) return;int L = s->l, R = s->r, C = s->c;S.erase(s); S.insert({L,p,C}); S.insert({p+1,R,C}); } void update(int L, int R, int C) {split(L-1); split(R);while(1) {auto s = S.lower_bound({L,L});if(s == S.end() || (s->l) > R) break;if(s->c) {-- ans[col[s->c]];col[s->c] -= s->r - s->l + 1;++ ans[col[s->c]];}S.erase(s);}-- ans[col[C]];col[C] += R-L+1;++ ans[col[C]];S.insert({L,R,C}); } void solve(int u, int c) {while(u > 1) {int L = max(id[top[u]],2), R = id[u];if(L <= R) update(L,R,c);u = fa[top[u]];} } int main() {read(n), read(C), read(Q);rep(i,2,n) { int u, v;read(u), read(v);G[u].pb(v), G[v].pb(u);}dfs1(1,0); dfs2(1,1);ans[0] = C;S.insert({2,n,0});while(Q--) { int u, c, m;read(u), read(c), read(m);solve(u,c);printf("%d\n",ans[m]);} }

轉載于:https://www.cnblogs.com/RRRR-wys/p/10487085.html

總結

以上是生活随笔為你收集整理的Gym102059A Coloring Roads的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。