bzoj 4196 [Noi2015]软件包管理器 (树链剖分+线段树）
4196:[Noi2015]软件包管理器TimeLimit: 10Sec MemoryLimit: 512MBSubmit: 2852 Solved: 1668[Submit][Status][Discuss]DescriptionLinux用户和OSX用户一定对软件包管理器不会陌生。通过软件包...
BZOJ3626[LNOI2014]LCA——树链剖分+线段树
题目描述给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出lrz，求sigma_{l<=i<=r}dep[LCA(i,z)]。（即，求在[l,...
【树链剖分】[BZOJ1036][ZJOI2008]树的统计Count
题目描述一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：I.CHANGEut:把结点u的权值改为tII.QMAXuv:询问从点u到点v的路径上的节点的最大权值III.QSUMuv:询问从点u到点v的路径上的节点的权值和注意：从点u到点v的...
【 Gym - 101138J 】Valentina and the Gift Tree(树链剖分)
BUPT2017wintertraining(15)4DGym-101138J数据题意n个节点的一棵树，每个节点的权值为g，q个询问，树上的节点U-V，求U到V的路径的最大子段和。题解先考虑这么一个问题：求区间[L,R]的最大子段和。q个询问，用线段树可以做到每个询问的时间是O(logn)。线段树的...
树链剖分边权模板spoj375
树链剖分是树分解成多条链来解决树上两点之间的路径上的问题如何求出树链：第一次dfs求出树上每个结点的大小和深度和最大的儿子，第二次dfs就能将最大的儿子串起来并hash（映射）到线段树上（或者其他数据结构上），这就是一条重链。一些性质：1.在树链上进行的算法要额外乘以一个logn：因为找u，v的lc...
BZOJ 1146: [CTSC2008]网络管理Network 树链剖分+线段树+平衡树
1146:[CTSC2008]网络管理NetworkTimeLimit: 50Sec MemoryLimit: 162MBSubmit: 870 Solved: 299[Submit][Status]DescriptionM公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为...
洛谷P4338 [ZJOI2018]历史（LCT，树形DP，树链剖分）
洛谷题目传送门ZJOI的考场上最弱外省选手T210分成功滚粗。。。。。。首先要想到30分的结论说实话Day1前几天刚刚刚掉了SDOI2017的树点涂色，考场上也想到了这一点想到了又有什么用？反正想不到最大的贡献是怎么推出来的然后晚上心中怀着九条CNM看完了Solution.pdf貌似对我这个蒟蒻来说...
【bzoj3589】动态树 树链剖分+树链的并
题解：树链剖分是显然的问题在于求树链的并比较简单的方法是用线段树打标记覆盖，查询标记区间大小Qlog^2n代码：#include<bits/stdc++.h>usingnamespacestd;#defineILinline#definerintregisterint#definerep...
poj 2763 Housewife Wind（树链剖分+单点查询+区间修改）
题目链接：?id=2763题意：给一个数，，边之间有权值，然后两种操作，第一种：求任意两点的权值和，第二，修改树上两点的权值。题解：简单的树链剖分。#include<iostream>#include<cstdio>#include<cstring>usingna...
UVALive 7338 （树链剖分+线段树）
Problem TollManagementIV题目大意给一张n个点m条边的无向图，有边权。数据保证前n-1条边构成了一棵最小生成树。要求对于每条边求出其边权上下最多浮动范围，使得最小生成树的形态不变（每次只改变一条边的权值）。n<=10000,m<=1000000解题分析我们称在最小生...
[SPOJ - QTREE] Query on a tree（树链剖分 - 边权最大值）
题目传送门：[SPOJ-QTREE] Queryonatree 题目大意：存在一个树，树上有n个节点和n-1条边，对这棵树进行以下两种操作CHANGE i ti ：将树的第i条边的权值改为tiQUERYa b：查询a->b路径中权值最大的边的值分析：边权树链剖分裸题，CHANGE操作是更改第i...
Bzoj 1036: [ZJOI2008]树的统计Count 树链剖分,LCT
1036:[ZJOI2008]树的统计CountTimeLimit: 10Sec MemoryLimit: 162MBSubmit: 11102 Solved: 4490[Submit][Status][Discuss]Description一棵树上有n个节点，编号分别为1到n，每个节点都有一个...
hdu 3966 Aragorn's Story（树链剖分+树状数组/线段树）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3966题意：给出一棵树，并给定各个点权的值，然后有3种操作：IC1C2K:把C1与C2的路径上的所有点权值加上KDC1C2K：把C1与C2的路径上的所有点权值减去KQC：查询节点编号为C的权值分析：典型的...
LightOJ 1348 （树链剖分 + 线段树（树状数组））
题目Link分析典型的树链剖分题，树链剖分学习资料Code#include<bits/stdc++.h>usingnamespacestd;constintmaxn=30000+131;structEdge{intNext;intTo;}edge[maxn<<1];intHe...
HDU3966(树链剖分)
题目：Aragorn'sStory题意：给一棵树，并给定各个点权的值，然后有3种操作：IC1C2K:把C1与C2的路径上的所有点权值加上KDC1C2K：把C1与C2的路径上的所有点权值减去KQC：查询节点编号为C的权值分析：典型的树链剖分题目，先进行剖分，然后用线段树去维护即可，注意HDU的OJ采用...
poj 2763 Housewife Wind （树链剖分）
题目链接：http://poj.org/problem?id=2763题意：给定一棵含n个结点的树和树的边权，共有q次操作，分为两种0c：求从位置s到c的距离，然后s变成c1ab:把第a条边的权值变为b分析：树链剖分，注意查询后要改变起点代码如下：#include<iostream>#i...
【BZOJ-2836】魔法树 树链剖分
2836:魔法树TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 323 Solved: 129[Submit][Status][Discuss]DescriptionInputOutputSampleInput40112234Add131Query0Quer...
bzoj 3672: [Noi2014]购票 树链剖分+维护凸包
3672:[Noi2014]购票TimeLimit:30Sec MemoryLimit:512MBSubmit:480 Solved:212[Submit][Status][Discuss]Description 今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国n个城市的OIer们都会从...
【POJ3237】Tree 树链剖分+线段树
【POJ3237】TreeDescriptionYouaregivenatreewith N nodes.Thetree’snodesarenumbered1through N anditsedgesarenumbered1through N −1.Eachedgeisassociatedwitha...
洛谷P3128 [USACO15DEC]最大流Max Flow [树链剖分]
题目描述FarmerJohnhasinstalledanewsystemof pipestotransportmilkbetweenthe stallsinhisbarn(),convenientlynumbered .Eachpipeconnectsapairofstalls,andallst...