zsj6315的博客

$A$题：CF1098A

给你一棵树，树根为$1$号点。每个点$i$有一个非负整数权值$a_i$，记点$i$到根的路径上经过的所有点（包括根和自身）的权值总和为$s_i$。

现在擦去所有深度为偶数的点的$s_i$，求$\sum a_i$最小可能是多少，如果无解，输出$-1$。

被擦去的$s_i$在输入文件中被替换为$−1$。

$B$题：CF1286B

有一棵形态确定的有根树，结点编号为$1,\cdots,n$每个结点$i$有权值$a_i$。

定义$c_i$表示：满足$j$在$i$子树内且$a_j < a_i$的$j$的个数。

现在给定所有的$c_i$，请你构造一种$a_i$的方案使得所有$c_i$成立，你构造的方案要满足$1\leq a_i\leq 10^9$且$a_i$ 是整数。

输入中，第一行为表示结点数量的$n(n \leq 2000)$，之后$n$行中第$i$行两个整数依次为$p_i$和$c_i$，$p_i$表示$i$的父结点，根节点的$p_i=0$。

若存在一组$a_i$ 满足方案，第一行输出 YES 并在第二行依次输出所有$a_i$；否则输出一行 NO。

$C$题：CF698B

给你一个数组$p$，让你修改它使它变成一个有效数组。

其中数组有效是指：

1.其对应一棵树。

2.有且只有一个索引$r$，符合$p_r=r$。其中顶点$r$是树的根。

3.对于其余的$\forall i$,$i$与$p_i$之间有边

请你输出最小修改次数，及一种修改方案（输出修改后数组）。

$D$题：CF29D

蚂蚁想要访问树中的每个节点并返回到根，每条边都要恰好经过两次。此外，他想以特定的顺序访问节点。你要找到蚂蚁的可能路线。

输入：

第一行包含整数$N$ $(3 \le N \le 300)$代表树中的顶点数量。接下来的$N-1$行描述边。每个边用两个整数来描述，即它连接的顶点的编号。均为无向边。顶点从$1$开始编号，$1$是根节点。最后一行包含$k$个整数，其中$k$是树中叶子的数量。这些数字描述了叶节点应该被访问的顺序。保证每个叶节点只出现一次。

输出：

如果所需的路径不存在，输出$-1$。否则，输出$2N-1$个数字，描述路径。每次蚂蚁到达一个节点时，输出它的编号。

$E$题：CF260D

树中的每个节点都涂成黑色或白色，不会有两个颜色相同的节点通过边连接。每条边都包含写在其上的非负整数值。

一个坏男孩 Vasya 走到黑板上并在每个节点$v$附近写下数字$s_v$——所有与该节点相关的边的值的总和。然后 Vasya 从板上取下边和它们的值。

您的任务是通过节点颜色和数字$s_v$恢复原始树（给出任意方案即可，保证有解）。

$F$题：CF1566E

对于一棵有根树，定义一个节点$i$是叶子结点，仅当$i$没有子节点。

进一步定义一个节点$i$是“可移动节点”，仅当$i$不是根、不是叶子节点且其所有直接相连的子节点都是叶子结点。

你可以对任意“可移动节点”$i$进行下列操作任意次：

断开$i$与其父亲节点的边，选择任意一个不属于节点$i$及其子树的节点$j$并在$i$,$j$间连边。

给定一棵以节点$1$为根的$n$个节点的有根树，求经过若干次操作后，这棵树最少有几个叶子结点。$T$组数据。

$1≤T≤10^4$,$1≤n$,$∑n≤2×10^5$

给定的是棵树.

$G$题：CF1586E

给定一个$n$个点$m$条边的无向连通图，无重边自环。

给出$q$个形如$x$ $y$的操作，你要选定一条从$x$到$y$的路径，并将其上所有边的权值(初始为$0$)$++$。

要求$q$次操作完后，所有边边权为偶数。

如果可以，输出YES并给出一组方案。

否则输出NO，并回答至少添加多少个额外的询问才能有合法方案。

各处P来的翻译qwq

博客

题目收录

CF套题4翻译