\(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,整数,uoj,节点,套题 From: https://www.cnblogs.com/zsj6315/p/18434948