标签 - 点分治

TCO的神题真的做不动了 不如换换脑袋吧 E Palindromes in a Tree 题意:给你一棵N" role="presentation" style="position: relative;">NNN个点的树,每一个点有一个字母′a′−′t′" role="presentation" style="position: relative;">′a′−′t′′a′−′t′'a'-'t',对每个点回答有多少经过它的路径是回文的。一条路径回文当且仅当它的
? 解题记录 ? ? 洛谷 ? ? 点分治 ? ? 贪心 ? ? 哈希 ? ? stl ?    2018-10-06 17:42:56    457    0    0
题解 for D:希望 D.pdf 我们来看看这道题的部分分: 首先明确本题的贪心策略:一旦有放置魔法符文的方案就放,这个贪心策略是显然正确的。 对于Subtask1" role="presentation" style="position: relative;">Subtask1Subtask1Subtask1:枚举树上O(N2)" role="presentation" style="position: relative;">O(N2)O(N2)O(N^2)条路径,每一条路径都O(N)" role="presentation" style="position: re
? 解题记录 ? ? 洛谷 ? ? 点分治 ? ? FFT|NTT ?    2018-07-24 18:45:25    535    0    0
Problem description.You are given a tree. If we select 2 distinct nodes uniformly at random, what's the probability that the distance between these 2 nodes is a prime number? InputThe first line contains a number N: the number of nodes in this tree. The following N-1 lines contain pairs a[i] and b[i
? 解题记录 ? ? 洛谷 ? ? 点分治 ? ? 点分树 ? ? 堆 ?    2018-05-26 22:06:41    525    0    0
题目描述给出一棵边带权的节点数量为n的树,初始树上所有节点都是白色。有两种操作: C x,改变节点x的颜色,即白变黑,黑变白 A,询问树中最远的两个白色节点的距离,这两个白色节点可以重合(此时距离为0)。 输入输出格式输入格式:  In the first line there is an integer N (N <= 100000) In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a,
? 解题记录 ? ? 洛谷 ? ? 点分治 ? ? 点分树 ? ? 堆 ?    2018-05-26 21:49:01    578    0    0
题目描述Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。 游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。 我们将以如下形
? 解题记录 ? ? HDU ? ? 点分治 ?    2018-04-23 21:04:15    432    0    0
Problem DescriptionThere is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a vertex). Today the students under t
? 解题记录 ? ? 洛谷 ? ? 点分治 ?    2018-04-23 20:56:17    470    0    0
题目描述给一棵树,每条边有权。求一条简单路径,权值和等于 K ,且边的数量最小。 输入输出格式输入格式:   第一行:两个整数 n,k 。 第二至 n 行:每行三个整数,表示一条无向边的两端和权值 (注意点的编号从 0 开始)。   输出格式:   一个整数,表示最小边数量。 如果不存在这样的路径,输出 -1 。   输入输出样例输入样例#1: 复制4 3 0 1 1 1 2 2 1 3 4 输出样例#1: 复制2 说明n≤20000
? 解题记录 ? ? POJ ? ? 点分治 ?    2017-08-17 22:14:47    354    0    0
TreeTime Limit: 1000MS Memory Limit: 30000KTotal Submissions: 23648 Accepted: 7836 Description Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for ev