标签: 图论

「CodeForces 1270G」Subset with Zero Sum

You are given 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛, such that for each 1≤𝑖≤𝑛 holds 𝑖−𝑛≤𝑎𝑖≤𝑖−1.

Find some nonempty subset of these integers, whose sum is equal to 0. It can be shown that such a subset exists under given constraints. If there are several possible subsets with zero-sum, you can find any of them.

「CodeForces1278D&E」Segment Tree & Tests for problem D

As the name of the task implies, you are asked to do some work with segments and trees.

Recall that a tree is a connected undirected graph such that there is exactly one simple path between every pair of its vertices.

You are given 𝑛 segments [𝑙1,𝑟1],[𝑙2,𝑟2],…,[𝑙𝑛,𝑟𝑛], 𝑙𝑖<𝑟𝑖 for every 𝑖. It is guaranteed that all segments' endpoints are integers, and all endpoints are unique — there is no pair of segments such that they start in the same point, end in the same point or one starts in the same point the other one ends.

「CodeForces 1277E」 Two Fairs

There are 𝑛 cities in Berland and some pairs of them are connected by two-way roads. It is guaranteed that you can pass from any city to any other, moving along the roads. Cities are numerated from 1 to 𝑛.

Two fairs are currently taking place in Berland — they are held in two different cities 𝑎 and 𝑏 (1≤𝑎,𝑏≤𝑛; 𝑎≠𝑏).

「16届同大邀请赛」 后花园的树

菜哭武的后花园里种着一棵树,这棵树有n个节点和n-1条边,每个节点都涂着一种颜色。菜哭武打算在接下来的m天里,每天执行以下两个操作之一:
1.菜哭武选择某一种颜色和树上的某一个节点,将这个节点涂上这种颜色(会将该节点原有的颜色覆盖)
2.菜哭武选择一种颜色,然后询问这棵树上所有涂着这种颜色的节点构成的子树含有多少个节点,(原树上的某个点集S构成的子树T的定义是:
如果u∈S,v∈S,那么原树u和v路径上的所有点都属于这棵子树T)。如果这棵树上没有这种颜色的节点,那么定义询问的结果为0。