7588: Linuber File System

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:1

题目描述

It is preferrable to read the pdf statment.

The Linuber File System, which is designed by Cuber QQ, has a sophisticated privilege management system. Specifically, each file is associated with a confidential score (an integer), and only users with access level greater than or equal to the confidential score of the file can access that file.

LFS also organizes files in a directed tree, like normal file systems (e.g., NTFS, Ext4 and APFS) do. One subtle difference is that, in LFS, everything is file. Some files are linked with some other files as its \textit{subfiles}, but they are considered as files instead of directories as they are associated with data on their own.

One advantage of using LFS is that, it has a really flexible management of privileges. For example, when a file becomes more or less confidential, one can increase/decrease its confidential score. At the same time, the confidential scores of its subfiles, sub-subfiles and so on will be updated accordingly. This can be thought of as an advantage, or a side effect, depending on your need. A mathematical model is, given a directed tree, you can pick any node u on the tree, and add x (positive or negative, possibly zero) to the values for each node in the subtree of u.

Given a LFS with confidential scores at 0 for all files, you are asked to perform the above operation as few times as possible, to make sure the confidential score of file i lies in the interval [li,ri] for all 1≤i≤n, where n is the number of files in this system. In other words, the file i should not be accessible to users with access level lower than li, but people with level at least ri will have their access guaranteed.

输入格式

The very first line contains an integer T (1≤T≤10), denoting the number of test cases.

Each test case begins with a single integer n (2≤n≤2 000), denoting the number of files.

In the next n−1 lines, each line contains two space-separated integers ui,vi (1≤ui,vi≤n), denoting the endpoints of each linkage. It is not clear whether ui is a subfile of vi or vi is a subfile of ui. You should infer that on your own, as it is known that 1 is the root file, i.e., file with no parent file.

In the next n lines, each line contains two space-separated integers li,ri (−109≤li≤ri≤109), denoting the required confidential score interval for file i.

输出格式

For each test case, print a single line containing an integer, which is the answer.

输入样例 复制

2
3
1 2
1 3
-2 -1
-3 -2
-1 -1
6
1 5
2 4
2 1
1 3
3 6
-2 4
-3 2
4 5
2 2
-5 -1
-1 4

输出样例 复制

2
3

分类标签