xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共5篇）

CodeForces 593D Happy Tree Party [LCA+并查集]

题意：给一棵树，每条边有一个权值，给两种操作，第一种是询问y向下整除从a到b的最短路径中每条边的权值后y的值，第二种是改变某条边的权值。思路：y的最大值为1e18，最多除大于等于2的数不超过60次即可将y变为0，先dfs以任意一点为根建树，记录每个点的深度和它的父结点并将边权转化为点权，再搞...

codeforces LCA 并查集 acm 算法

2019-04-08

0 366

2019南昌网络赛 J Distance on the tree 主席树+lca

题意给一颗树，每条边有边权，每次询问\(u\)到\(v\)的路径中有多少边的边权小于等于\(k\) 分析在树的每个点上建\(1\)到\(i\)的权值线段树，查询的时候同时跑\(u,v,lca(u,v)\)三个版本的线段树，查询\(1\)到\(k\)的树上差分和\(val[u]+...

主席树 LCA

2019-05-23

0 412

gym-102082，2018-2019, ICPC, Asia Yokohama Regional Contest 2018 J Colorful Tree

题意给定一个\(n\)个点的树，每个点有个初始颜色\(c_i\)，有\(m\)次询问，询问有两种： \(U~x_k~y_k\)，将第\(x_k\)个点的颜色改为\(y_k\)。 \(Q~y_k\)，找到一个边数最少的子图，使得这个子图包括所有颜色为\(y_k\)的点，输出这个子图的边...

树链剖分 LCA

2020-06-29

0 653

CodeForces 593D Happy Tree Party [LCA+并查集]

题意：给一棵树，每条边有一个权值，给两种操作，第一种是询问y向下整除从a到b的最短路径中每条边的权值后y的值，第二种是改变某条边的权值。思路：y的最大值为1e18，最多除大于等于2的数不超过60次即可将y变为0，先dfs以任意一点为根建树，记录每个点的深度和它的父结点并将边权转化为点权，再搞...

codeforces LCA 并查集 acm 算法

2019-04-08

0 479

2019南昌网络赛 J Distance on the tree 主席树+lca

题意给一颗树，每条边有边权，每次询问\(u\)到\(v\)的路径中有多少边的边权小于等于\(k\) 分析在树的每个点上建\(1\)到\(i\)的权值线段树，查询的时候同时跑\(u,v,lca(u,v)\)三个版本的线段树，查询\(1\)到\(k\)的树上差分和\(val[u]+...

主席树 LCA

2019-05-23

0 386