Ag 组 T1 题目描述 一棵树，点有点权，每次操作可以将选择两个相邻的点 $u,v$，并指定权值 $w$，让 $u$ 权值减 $w$，$v$ 权值加 $w$，求最少操作次数使得所有点的点权均相等，并构造方案。 解法 容易发现，点权和不变，可算出最终每个点应该得到的权值。如果一条边连接的两个连通块一边多余，一边不足，则这个边无论如何都要操作，而如果两边权值都恰好，则不用对这条边进行操作。构造方案随

在太阳西斜的这个世界里， 置身天上之森。 等这场战争结束之后， 不归之人与望眼欲穿的众人， 人人本着正义之名， 长存不灭的过去、逐渐消逝的未来。 我回来了， 纵使日薄西山， 即便看不到未来， 此时此刻的光辉， 盼君勿忘。 ————世界上最幸福的女孩 P5064 [Ynoi2014] 等这场战争结束之后 简要题意 双倍经验：LOJ 519 给定一个 $n$ 个点的无向图，点有点权，最开始没有边，

前言 LCT（Link Cut Tree） 支持在森林中动态加边、删边、维护链上信息的数据结构。基于 Splay 和实虚链剖分。请确保你对链剖分以及 Splay 有所了解。 实虚链剖分 同轻重链剖分，每个节点都有实虚两种属性。每个节点最多有 $1$ 个实儿子，从父亲到实儿子的边称为实边，从父亲到虚儿子的边称为虚边，一条由实边构成的极长的链称为实链。与轻重链剖分不同的是节点的实虚是动态指定的，并且一

别叹息太多告别，至少相遇很真切。 摇曳着盛放枯竭，时间从未停歇。 天涯浪迹的白雪，念念不忘山川蝴蝶。 听说有人孤负黑夜，偏要点亮人间的月。 简要题意 定义运算 $a \operatorname{nand} b$ 为 $\operatorname{not}(a \operatorname{and} b)$，$\operatorname{and}$ 指按位与，$\operatorname{not}

第一次在场上做出月赛交互题。 题意简述 在一个长为 $n$ 的数列中，有两个特殊数字，你需要找到这两个数的下标，每次你可以向交互库询问一个集合，如果这个集合中恰好有 $1$ 个特殊数字，交互库返回 $1$，否则交互库返回 $0$。$n\le 1000$，最多向交互库询问 $19$ 次。 思路 首先，在值域上是做是不方便的，假如每次询问一个前缀区间，那么必然答案在中间一段才会是 $1$，普通的二分和

题意简述 一个 $H\times W$ 的矩形区域，某些格子上会有障碍，你可以在没有障碍的格子上放置任意个摄像头，摄像头可以朝向上下左右四个方向，每个摄像头能监视到的区域是从当前格子开始，向该摄像头的方向延伸直到边界或者障碍物的区域，求至少需要多少个摄像头才能让所有没有障碍的格子都被监视到。 $1\le H,W\le300$，时间限制 $\rm{2s}$，内存限制 $\rm{1GB}$。 思路

题目描述 一棵 $n$ 个结点的有根树，其中结点编号为 $1\sim n$，而 $1$ 号点就是根节点。初始时，树只有一号点，而心也在一号点。之后每一步，树都会长出一个新结点，即某个和当前已经存在的某个结点相邻的结点被加入了树中，之后，心会沿着心到新加结点的简单路径移动一步。这棵 $n$ 个结点的树有很多种生长的顺序，不同的顺序可能会导致最终心的位置不同。求哪些结点可能是心在生长过程结束时停留的位

简介 此处定义更新复杂度为单次移动 $l,r$ 指针所需的时间复杂度，查询复杂度为当莫队左右端点移动到查询位置时获得答案所需的时间复杂度。 当莫队更新时间复杂度较高而查询复杂度较低时，莫队二次离线能平衡时间复杂度。本质上是将普通莫队 $O(n\sqrt n)$ 次更新，$O(n)$ 次查询平衡为 $O(n)$ 次更新，$O(n\sqrt n)$ 次查询。 莫队二次离线要求贡献具有可减性，并且查询复

题意简述 给定一棵 $n$ 个点的以 $1$ 为根的树。 有 $m$ 条路径 $(x,y)$，保证 $y$ 是 $x$ 或 $x$ 的祖先，每条路径有一个权值。 你要在这些路径中选择若干条路径，使它们能覆盖每条边，同时权值和最小。 $n,m\le3\times10^5$。时限 $\rm{4s}$，内存限制 $\boldsymbol{\rm{256MB}}$。 Part 1 朴素 DP 记 $g_u