1. NOIP2016 Day1T2 天天爱跑步
2. NOIP2015 Day2T3 运输计划
3. NOIP2013 Day1T3 货车运输
4. NOIP2012 Day2T3 疫情控制
5. NOIP2014 Dau1T2 联合权值

基本不是什么很好写的题

## ARC083E - Bichrome Tree

Time limit : 2sec / Memory limit : 256MB
Score : 700 points

### Problem Statement

We have a tree with $N$ vertices. Vertex 1 is the root of the tree, and the parent of Vertex $i$ ($2≤i≤N$) is Vertex $P_i$.
To each vertex in the tree, Snuke will allocate a color, either black or white, and a non-negative integer weight.
Snuke has a favorite integer sequence, $X_1$,$X_2$,…,$X_N$, so he wants to allocate colors and weights so that the following condition is satisfied for all $v$.

• The total weight of the vertices with the same color as $v$ among the vertices contained in the subtree whose root is $v$, is $X_v$.

Here, the subtree whose root is $v$ is the tree consisting of Vertex $v$ and all of its descendants.

Determine whether it is possible to allocate colors and weights in this way.

### Constraints

• $1≤N≤1000$
• $1≤P_i≤i−1$
• $0≤X_i≤5000$

### Inputs

Input is given from Standard Input in the following format:

### Outputs

If it is possible to allocate colors and weights to the vertices so that the condition is satisfied, print POSSIBLE; otherwise, print IMPOSSIBLE.

### Sample Output 1

For example, the following allocation satisfies the condition:

• Set the color of Vertex 1 to white and its weight to 2.
• Set the color of Vertex 2 to black and its weight to 3.
• Set the color of Vertex 3 to white and its weight to 2.

There are also other possible allocations.

### Sample Output 2

If the same color is allocated to Vertex 2 and Vertex 3, Vertex 2 cannot be allocated a non-negative weight.

If different colors are allocated to Vertex 2 and 3, no matter which color is allocated to Vertex 1, it cannot be allocated a non-negative weight.

Thus, there exists no allocation of colors and weights that satisfies the condition.

### 题解

$n$ 个点, $1$ 为根节点然后读入第 $2$~$n$ 个点的父节点

$n$ 个数字 $X_i$，要求给每个点赋予黑色或白色和权值，满足对于每个点 $v$，子树$v$中和$v$同色的点的权值和等于$X_v$。每个点的点权任意.

## CF739 B. Alyona and a tree

Alyona has a tree with $n$ vertices. The root of the tree is the vertex $1$. In each vertex Alyona wrote an positive integer, in the vertex i she wrote $a_i$. Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges).

Let’s define $dist(v,u)$ as the sum of the integers written on the edges of the simple path from $v$ to $u$.

The vertex $v$ controls the vertex $u$ $(v ≠ u)$ if and only if u is in the subtree of $v$ and $dist(v,u) ≤ a_u$.

Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex $v$ what is the number of vertices $u$ such that $v$ controls $u$.

### Input

The first line contains single integer $n$ ($1 ≤ n ≤ 2*10^5$).

The second line contains $n$ integers $a_1$, $a*_2$, …, $a_n$ ($1 ≤ a_i ≤ 10^9$) — the integers written in the vertices.

The next ($n - 1​$) lines contain two integers each. The $i​$-th of these lines contains integers $p_i​$ and $w_i​$ ($1 ≤ p_i≤ n​$, $1 ≤w_i ≤ 10^9​$) — the parent of the ($i + 1​$)-th vertex in the tree and the number written on the edge between $p_i​$ and ($i + 1​$).

It is guaranteed that the given graph is a tree.

### Output

Print $n$ integers — the $i$-th of these numbers should be equal to the number of vertices that the $i$-th vertex controls.

### Note

In the example test case the vertex 1 controls the vertex 3, the vertex 3 controls the vertex 5 (note that is doesn’t mean the vertex 1 controls the vertex 5).

## 855C. Helga Hufflepuff’s Cup

Harry, Ron and Hermione have figured out that Helga Hufflepuff’s cup is a horcrux. Through her encounter with Bellatrix Lestrange, Hermione came to know that the cup is present in Bellatrix’s family vault in Gringott’s Wizarding Bank.

The Wizarding bank is in the form of a tree with total n vaults where each vault has some type, denoted by a number between 1 to m. A tree is an undirected connected graph with no cycles.

The vaults with the highest security are of type k, and all vaults of type k have the highest security.

There can be at most x vaults of highest security.

Also, if a vault is of the highest security, its adjacent vaults are guaranteed to not be of the highest security and their type is guaranteed to be less than k.

Harry wants to consider every possibility so that he can easily find the best path to reach Bellatrix’s vault. So, you have to tell him, given the tree structure of Gringotts, the number of possible ways of giving each vault a type such that the above conditions hold.

### Input

The first line of input contains two space separated integers, n and m — the number of vaults and the number of different vault types possible. (1 ≤ n ≤ 105, 1 ≤ m ≤ 109).

Each of the next n - 1 lines contain two space separated integers u**i and v**i (1 ≤ u**i, v**i ≤ n) representing the i-th edge, which shows there is a path between the two vaults u**i and v**i. It is guaranteed that the given graph is a tree.

The last line of input contains two integers k and x (1 ≤ k ≤ m, 1 ≤ x ≤ 10), the type of the highest security vault and the maximum possible number of vaults of highest security.

### Output

Output a single integer, the number of ways of giving each vault a type following the conditions modulo 109 + 7.

### Note

In test case 1, we cannot have any vault of the highest security as its type is 1 implying that its adjacent vaults would have to have a vault type less than 1, which is not allowed. Thus, there is only one possible combination, in which all the vaults have type 2.