#树上

树上差分

前置芝士:here树上差分:典型问题描述:给定一棵有N个点的树,所有节点的权值初始时都为0。 有K次操作,每次指定两个点u , v,将 u 到 v 路径上所有点的权值都+1。 请输出K次操作完毕后权值最大的那个点的权值。朴素思路:不用多想,...
代码星球 ·2020-12-28

HDU 2196 Computer(求树上每一个节点到其他点的最远距离)

解题思路:求出树的直径的两个端点。则树上每一个节点到其它点的最远距离一定是到这两个端点的距离中最长的那一个。#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cm...

UOJ#370. 【UR #17】滑稽树上滑稽果 动态规划

原文链接www.cnblogs.com/zhouzhendong/p/UOJ370.html首先易知答案肯定是一条链,因为挂在链的最下面肯定比挂在其他节点上赚。问题被转化成了从一个集合中不断选数加入到当前序列尾端,使得序列的所有前缀AND之和最小。我们发现,假如加入一个数后可以使序列的AND值变小,那么必然不会去加一个...

UOJ#33. 【UR #2】树上GCD 点分治 莫比乌斯反演

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ33.html  首先我们把问题转化成处理一个数组ans,其中ans[i]表示d(u,a)和d(v,a)同时为i的倍数的(u,v)个数。(最后求答案的时候只要莫比乌斯反演回来就好了。)  注意一下我的代码中对于(u,v)有祖先关...

BZOJ3052/UOJ#58 [wc2013]糖果公园 莫队 带修莫队 树上莫队

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ3052.html  给定一棵树,有$n$个节点。有$m$种颜色,第$i$个节点的颜色为$c_i$。  给定参数$v_{1},v_2,cdots,v_m$和$w_1,w_2,cdots,w_n$,具有以下意义:    第$i$...

BZOJ4034 [HAOI2015]树上操作 树链剖分

有一棵点数为N的树,以点1为根,且树点有边权。然后有M个操作,分为三种:操作1:把某个节点x的点权增加a。操作2:把某个节点x为根的子树中所有点的点权都增加a。操作3:询问某个节点x到根的路径中所有点的点权和。   树链剖分。  然后对于子树修改,我们可以考虑dfs序。  树链剖分也是一种dfs序。  单点修...

动态规划-树上dp-1757. 搜集钻石

2020-04-08 08:05:15问题描述:蒜国有 n 座城市,编号从 1 到 n,城市间有 n−1 条道路,且保证任意两座城市之间是连通的。每一座城市有一定数量的钻石。蒜头君想在蒜国搜集钻石。他从城市 1&nbs...

CF817F MEX Queries(线段树上二分)

维护一个01串,一开始全部都是03种操作1.把一个区间都变为12.把一个区间都变为03.把一个区间的所有数字翻转过来每次操作完成之后询问区间最小的0的位置l,r<=10^18区间操作想到线段树,离散化不用说,l,r太大了。1,2,3操作非常好维护。然后在查询中二分查询就好了。一开始看别的博客说要加1节点和r+1节...