网站icp备案系统下载,企业网站定制公司,企业信息化平台建设方案,网站开发排期表模板Gym102059A Coloring Roads 题意#xff1a;\(n\)点的树#xff0c;一开始每条边都没有颜色#xff0c;有\(Q\)个操作#xff0c;每次将从\(u\)到\(1\)路径上的所有边全部染色为颜色\(c\)#xff0c;之后询问整棵树上#xff0c;出现了\(m\)次的颜色有多少种。数据范围均… 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;
templateclass 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;
vectorint 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({p1,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-L1; 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
