[ P O I 2008 ] S T A − S t a t i o n ( 树形 d p ) \Huge{[POI2008] STA-Station(树形dp)} [POI2008]STA−Station(树形dp) 题目链接：[P3478 POI2008] STA-Station - 洛谷 文章目录 题意思路标程 题意 给定一个 n n n个点的树，请求出一个结点，使得

链接：https://www.luogu.com.cn/problem/P3478 来源：牛客网 题目描述 给定一个 nn 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。一个结点的深度之定义为该节点到根的简单路径上边的数量。 输入描述 第一行有一个整数，表示树的结点个数 nn。接下来 (n - 1)(n−1) 行，每行两个整数 u, vu,v，表示存在一条连接

Description 多边形相邻边垂直，边长为整数，边平行坐标轴。要在多边形的点上放一些激光发射器和接收器。满足下列要求： 1发射器和接收器不能放置在同一点； 2发射器发出激光可以沿壁反射，最终到达一个接收器； 3发射器只能沿角平分线发射激光。求：最多可放置多少对发射器和接收器？点数4<=n<=100000 Input 第一行给出一个数字N,代表有多少个点. 下面N行,用来描述点的

Description N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务. Input 第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000 Output

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=1131 题目大意 给定一棵树,找到一个根,使所有点的深度和最大 题解 树形DP 我们先把这棵树处理成以1为根的有根树 维护以每个点为根的子树的节点数 size[] size[] 我们逐层 O(1) O(1)查询 设 a=fa[b],且已知ans[a] a=fa[b],且已知a

Description 一个长度为n的记账单，+表示存￥1，-表示取￥1。现在发现记账单有问题。一开始本来已经存了￥p，并且知道最后账户上还有￥q。你要把记账单修改正确，使得 1：账户永远不会出现负数； 2：最后账户上还有￥q。你有2种操作： 1：对某一位取反，耗时x； 2：把最后一位移到第一位，耗时y。 Input The first line contains 5 integers n,

题目大意 给出一个平面内的n个点，有一系列询问形如: x0,y0,x1,y1 x_0,y_0,x_1,y_1，输出平面的点中更接近 (x0,y0) (x_0,y_0)的个数，更接近 (x1,y1) (x_1,y_1)的个数，与两点距离相等的点的个数。 主要思想 可以按照询问分6种情况讨论! 以上六种情况中， p1 p_1表示第一个点， p2 p_2表示第二个点，他们

【题解】P3469 [POI2008]BLO-Blockade 图论割点好题！ 题目链接 P3469 [POI2008]BLO-Blockade - 洛谷 题意概述 给定一张无向图，求每个点被封锁之后有多少个有序点对 \((x,y)(x \ne y,1 \le x,y \le n)\) 满足 \(x\) 无法到达 \(y\)。 思路分析 首先需要说明一个易错点，即有序点对，即 \((x,y)\)

Luogu 3469ACwing 365 题目分析： 对于一个点 u u u,分此点是否为割点进行讨论： 若 u u u不是割点，则将此点删除，其他 n − 1 n-1 n−1个点仍联通，则 u u u与其他 n − 1 n-1 n−1个点不连通，由于求的是有序点对 ( x , y ) (x,y) (x,y),则 a n s [ u ] = 2 ∗ ( n − 1 ) ans[u]=2