#P11526. [2024省队模拟]货车运输

    ID: 10674 传统题 2000ms 512MiB 尝试: 46 已通过: 3 难度: 9 上传者: 标签>CF2600图论树形DP组合数学构造最小生成树

[2024省队模拟]货车运输

【题目描述】

给出 nn 个点 mm 条边的无向连通图,边的编号为 1∼m1\sim m,边的权值是一个 1∼m1\sim m 的排列。

记 d(u,v)d(u,v) 为 u,vu,v 之间最大边权最小的路径中的最大边的编号。给出所有的 d(u,v)d(u,v),求有多少种给边赋值的方案符合限制(保证至少存在一种方案符合限制),答案对 109+710^9+7 取模。

【输入格式】

第一行两个整数,表示 n,mn,m。

第 2∼n2\sim n 行,第 ii 行为 i−1i-1 个整数,分别为 d(i,1),d(i,2),…,d(i,i−1)d(i,1),d(i,2),\dots,d(i,i-1) 。

第 n+1∼n+mn+1\sim n+m 行,每行两个整数 ui,viu_i,v_i ,表示一条连接 ui,viu_i,v_i 的无向边。(保证无重边、自环)

【输出格式】

一行一个整数,符合要求的赋值方案数目对 109+710^9+7 取模的余数。

【样例 #1】

输入:

3 2
2 
1 1 
3 2
2 1

输出:

1

【样例 #2】

输入:

4 5
5 
4 5 
2 2 2 
4 1
4 2
3 2
3 1
2 1

输出:

3

【样例 #3】

$见选手目录下的 \texttt{transport/transport3.in} 与 \texttt{transport/transport3.ans}$。

【样例 #3】

$见选手目录下的 \texttt{transport/transport4.in} 与 \texttt{transport/transport4.ans} 。$。

【数据范围和约定】

对于所有子任务,1≤n≤1000,1≤m≤40001 \leq n\leq 1000,1\leq m\leq 4000。

子任务编号 n≤n \leq m≤m \leq 分值
11 1010 n−1n-1 77
22 99 88
33 n(n−1)2\frac{n(n-1)}{2} 2020
44 100100 n−1n-1 1010
55 150150
66 10001000 n−1n-1 3030
77 40004000 1515