 NOIP2016 Day1T2 天天爱跑步
 NOIP2015 Day2T3 运输计划
 NOIP2013 Day1T3 货车运输
 NOIP2012 Day2T3 疫情控制
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 nonnegative 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:
1  N 
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 Input 1
1  3 
Sample Output 1
1  POSSIBLE 
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 Input 2
1  3 
Sample Output 2
1  IMPOSSIBLE 
If the same color is allocated to Vertex 2 and Vertex 3, Vertex 2 cannot be allocated a nonnegative 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 nonnegative weight.
Thus, there exists no allocation of colors and weights that satisfies the condition.
题解
题目地址http://arc083.contest.atcoder.jp/tasks/arc083_c
题意:
$n$ 个点, $1$ 为根节点然后读入第 $2$~$n$ 个点的父节点
$n$ 个数字 $X_i$，要求给每个点赋予黑色或白色和权值，满足对于每个点 $v$，子树$v$中和$v$同色的点的权值和等于$X_v$。每个点的点权任意.
1 

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.
Examples
Input1
1  5 
Output1
1  1 0 1 0 0 
Input2
1  5 
Output2
1  4 3 2 1 0 
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).
题解
题意：一棵根节点为 $1$ 的树，每个点都有点值 $a_i$，每条边也有权值，$dist(v, u)$ 表示从 $v$ 到 $u$ 边权和，当 $u$ 时 $v$ 的子树并且 $dist(v, u) \le a_u$ 时$u$ 就受 $v$ 控制，输出每个结点能控制的结点数。
首先，考虑每个点受到多少个点的影响，然后发现，点u并不是很好把贡献转移到父节点。于是就想每个点能影响到前面的多少个点，然后用vector记一下前缀和，然后lower_bound一下，看下能影响到哪个位置，树上差分一下就好了。
1 

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 ith 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.
Examples
Input
1  4 2 
Output
1  1 
Input
1  3 3 
Output
1  13 
Input
1  3 1 
Output
1  0 
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.
题解
题意：
给你 $n$个点，$n1$ 条边，让后给你个 $m$ ，再给你 $k$ 和 $x$ ，然后每个点可以是颜色 $1$~$k$ 有一个特殊颜色 $k$ 这个颜色最多出现 $x$次，然后和 $k$ 相邻的点颜色数值必须 $<k$ 求方案数
设 $dp_{i,j,k}$表示点 $i$ 颜色为 $j$ 整个子树 $i$ 有 $k$ 个点为特殊颜色的方案数
颜色范围这么大，显然不行，但是观察很容易发现，只有三种颜色：$
然后就可以推出转移方程，时间复杂度：$O(nk^2)$
1 
