_zidaoziyan的博客

题意: 2e5个点的无根树，每个点有点权，每条边有边权，定义一条简单路径的花费=这条路径两个端点点权的乘积+边权和， （一条简单路径可以包含一个点，这样花费是该点权的平方），最后问从每个点出发的最小花费思路: ans[i]=min(a[i]*a[j]+d[i]+d[j]) ->y=-a[i]*x+ans[i] 有三个点X,Y,Z,现在要求X的答案 假设Y比Z更优, 则X*Y+

题意: 给出一棵树，边长度都是1。每次任意取出两个点(u,v)，他们之间的长度为素数的概率为多大？思路: 树分治，对于每个根出发记录边的长度出现几次，然后求卷积，用素数表查一下即可添加答案。 时间复杂度:nlognlogn#include<bits/stdc++.h>using namespace std;const int N=5e4+100;struct Edge{ i

题意: 有N个顶点的树，节点间有权值， 节点分为黑点和白点。 找一条最长路径使得 路径上黑点数量不超过K个。思路: 设当前节点x到根的路径上黑色节点数量为deep[x],路径长度为dis[x] 将子节点按照最大deep倒序处理,利用启发式合并使得合并复杂度降为nlogn#include<bits/stdc++.h>template <class T1, class T2>inline

题意：给出一棵有根树（1为根），边有长度。每个点u有三个属性（len[u],p[u],q[u]）,每次u可以转移到u的某个祖先节点v（v满足dist(u,v)<=len[u]）, 代价为p[u]*dist(u,v)+q[u]。求每个点都转移到1的代价。思路: 树分治+cdq+维护凸壳1.树分治找出重心 2.处理重心到1的路径上的点 3.处理出重心的答案 4.维护len[u]-到重心的

传送门:Hdu 5469 Antonidas 题意:给你一棵树,有n个结点,每个结点有一个字母,找出一条链,它的字母组成为s,问有没有这样的链(n<=1e5) 思路: 对于一条链(u->v),可以分成u>lca(u,v),lca(u,v)->v,又因为对于树只能处理出lca(u,v)->u或者v的Hash值,所以我们刚开始对于s字符串的Hash要分成正向和反向 刚开始的时候用了map

传送门:Hdu 4918 Query on the subtree 题意：给出一颗n个点的树，每个点有一个权值，有两种操作，一种是将某个点的权值修改为v，另一种是查询距离点u不超过d的点的权值和。 思路: 最多有logn层的子树 对于每个点,最多属于logn个子树,那么我们可以预处理出每个点属于哪些重心以及到这些重心的距离,以每个重心建立树状数组, 每个点按照到不同重心的距离插

传送门:Hdu 5664 Lady CA and the graph 题意: 给你一个有n个点的树,给定根,叫你找第k大的特殊链 特殊的链的定义:u,v之间的路径,且lca(u,v)!=u&&lca(u,v)!=v,且路径第k大 思路:转自http://bestcoder.split.hdu.edu.cn/solutions.php?page=2 对于求第k大的问题，我们可以通

传送门:Hdu 5314 Happy King 题意： 给定N个点的树，点有权值,求多少个点对(u,v)满足u到v的路径上点权值最大值减最小值不大于给定的K 思路: 将点对分成经过根的和不经过根的,进行分治 每一次分治都维护点到根的最大值和最小值就可以了, 处理完一个子树的时候,利用容斥+二分查找左右范围就可以了 (路径上两点的较小值是两点到根较小的那个,较大值为两

参考:树分治论文 传送门:poj 1741 Tree 题意:给你一棵N(N<=10000)个节点的带权数,定义dist(u,v)为u,v两点之间的距离,再给定一个K (1<=K<=10^9),如果对于两个不同的节点a,b,如果满足dist(a,b,)<=k,则称(a,b)为合法点对, 求合法点对数目 思路:我们知道一条路径要么过根节点,要么在一棵子树中,所以我们可以利用分治

传送门:Tsinsen A1486. 树 题意:给你一棵树(n<=1e5),每个点有一个权值和喜欢不喜欢之分,找出一条路径至少包含K个喜欢的点,而且异或和最大 思路: 树分治,同时维护字典树 字典树每个点维护一个喜欢的点数的最大值 时间复杂度:nlogn*30#include<bits/stdc++.h>using namespace std;const int N=1