ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

7566: Animism

内存限制：512 MB 时间限制：15 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：0 通过：0
提交提交记录统计Web Board

题目描述

Notice：Don't output extra spaces at the end of one line.

Koishi loves Subterranean Animism(SA).

The map of SA is a undirected tree with n nodes and n−1 roads.

Koishi loves wander around SA by Rin's corpse cart. The cart use nuclear power. It take 1 point power to pass one road. Koishi has q wandering plan, in the i-th plan Koishi wants to wander from xi to yi, and the cart has pi points of power initially.

Obviously, in some plans, Koishi can't arrive the destination. To avoid this, Koishi asks Utsuho to set some nuclear-power filling station. There are m such stations. The i-th of them is located in the node ci and the level of this station is di. When Koishi arrive node ci, she can add (di−s) points of power to her cart or do nothing. Here s represents the amount of power the cart has currently.

For each plan, Koishi wants to know whether this plan can be finished successfully. Notice that she can pass the same road many times.

输入格式

The first line contains of a positive integer T(1≤T≤500), representing T test cases.

in each test case, the first line contains three positive integers n,m,q(1≤n,m,q≤105),representing the number of nodes, power stations and plans.

Each of the following n−1 lines contains two positive integers ui,vi, representing a road between ui and vi. It guarantees the input map is a tree.

Each of the following q lines contains three positive integers xi,yi,pi(1≤xi,yi≤n,1≤pi≤109). It describes the i-th plan.

Each of the following m lines contains two positive integers ci,di(1≤ci≤n,1≤di≤109). It describes the i-th power-stations.

There are at most 500 test cases and at most 12 test cases with n+m+q>5000

输出格式

For each test case, output q lines.

in the i-th line, if the i−th plan can be finished, output "YES", otherwise, output "NO"

输入样例 复制 

2
10 3 10
2 1
3 1
4 2
5 1
6 2
7 1
8 2
9 5
10 6
7 2 3
2 6 1
8 8 3
8 6 3
10 3 1
7 9 2
9 5 3
2 2 2
9 8 2
7 10 3
9 1
7 2
8 1
10 3 10
2 1
3 1
4 3
5 4
6 3
7 3
8 6
9 8
10 6
7 9 1
6 8 2
6 9 2
4 3 1
6 9 2
5 2 1
8 2 3
1 5 2
9 5 2
7 10 2
9 1
6 1
2 1

输出样例 复制 

YES
YES
YES
YES
NO
NO
YES
YES
NO
NO
NO
YES
YES
YES
YES
NO
NO
NO
NO
YES

分类标签