#3986. Tree and Sets

题目描述

有一棵n个结点的树，每条边有个长度leni (1≤leni≤10000)。

有q个点集，每个点集给定两个整数u,d (1≤u≤n,1≤d≤109)，表示所有与u的距离不超过d的点（包括u）在这个点集中。

两个点之间的距离为它们之间的最短路径的长度。

要求构造一个DAG（有向无环图），满足：

1、这个DAG至少有n+q个点，至多有1200000(1.2×106)个点和2400000(2.4×106)条边

2、对于每一条边u->v，u>n 且 u≠v

3、对于第i (1≤i≤q)个点集的每一个点x，第n+i个点到第x个点都有且仅有一条路径

4、对于不在第i (1≤i≤q)个点集的每一个点x，第n+i个点到第x个点都不存在路径

由于一些奇怪的原因，树上可能多了若干条边，但是这些边覆盖的树链不会重合，且不会存在自环。（即这棵树是仙人掌）

输入格式

第一行三个整数n,m,q，其中m表示这棵仙人掌上一共有m条边。

接下来m行，每行三个整数u,v,len，表示u和v之间有一条长度为len的无向边。

接下来q行，每行两个整数u,d，第i行表示第i个点集。

输出格式

第一行两个整数V,E，表示你构造的DAG的点数和边数。

接下来E行，每行两个整数u,v，表示u到v有一条有向边。

！！！请注意输出文件的大小，不能超过32MB，否则会显示TLE！！！

样例

样例输入

10 9 5  

2 1 9553  

3 2 8499  

4 3 5171  

5 1 7123  

6 3 1904  

7 5 5526  

8 7 5853  

9 6 6635  

10 8 7858  

6 4981  

7 14400  

3 21290  

4 9451  

10 16609

样例输出

15 19  

11 6  

11 3  

12 7  

12 5  

12 1  

12 8  

12 10  

13 3  

13 6  

13 9  

13 4  

13 2  

13 1  

14 4  

14 3  

14 6  

15 10  

15 8  

15 7

数据范围与提示

N<=10000,N-1<=m<=2*N-2,Q<=10000

尚无SPJ，请不要提交!