[已解决]【C++板块提升计划】梦想护卫舰 第15期 画树

sfqxx

你们顺着藏宝图的方向，走到了一个藏有10w鱼币的宝箱（剧情需要，请勿当真！）
但是！要想打开它，休想那么容易
这时，有两个人走了过来，他们能给你们一些提示……
但！需要作答两道超级难的题目
好了咱们先看题：
第一题：

玘给了寒一棵编号为 1～n 的树，这棵树上每个点都有一个点权，同时有些边有边权，有些边没有边权。可是玘把每一个点的点权删除了（真的6）。寒只知道点权都是整数，而且在 l 和 r 之间（包含端点）。而且，点权和边权有着下面的特殊关系：
对于有边权的边，要求连接的两个点的点权和为边权。
对于没有边权的边，无限制。
玘问寒这棵树有多少种不同的点权填写方式。两种填写方式不同，当且仅当至少存在一个点的点权不同。可是寒不会做这个题。

寒请你解决这个问题。回答正确即可获得第一条线索

输入格式：

本题有多组测试数据。

第一行一个整数 T，代表测试数据组数。

对于每一组测试数据：

第一行三个整数 n,l,r，代表树上点的个数是 n，点权的范围是 [l,r]。

接下来 n-1 行，每行先输入一个整数 op，op=0 表示这条边没有边权，op=1 表示这条边有边权。

如果 op=0，再输入两个整数 u,v，表示这条边连接 u,v两个点。

如果 op=1，再输入三个整数 u,v,w，表示有一条权值为 w 的边连接 u,v 两个点。

输出格式：
对于每个测试点，输出一行一个整数，代表点权填写方式的个数。答案对 10^9+7 取模。

输入与输出样例
输入：

1. 2
   
2. 6 0 4
   
3. 1 1 2 2
   
4. 1 2 3 4
   
5. 1 3 4 2
   
6. 0 2 5
   
7. 1 4 6 3
   
8. 
   
9. 6 -1 4
   
10. 1 1 2 4
    
11. 0 2 3
    
12. 0 3 4
    
13. 0 2 5
    
14. 0 4 6

复制代码

输出：

1. 5
   
2. 6480

复制代码

说明/提示
样例解释
对于样例的第一组测试数据，可以得到下图：

5种填写方式：
{0,2,2,0,0,3}
{0,2,2,0,1,3}
{0,2,2,0,2,3}
{0,2,2,0,3,3}
{0,2,2,0,4,3}
可以证明，不存在别的填写方式。

样例输入中，为了直观，添加了空行。实际数据中不存在多余空行。

数据范围

本题采用捆绑测试。

特殊性质：保证每条边都无边权。

对于 100% 的数据，保证 1≤T≤5，1≤n≤2×10^5
，1≤∑(求和，其实我没见过）n≤10 ^6，-10^9≤l≤r≤10^9
，-10^ 9≤w≤10 ^9
，op∈(这个不明白，谁知道在评论区回答可以获得1贡献）{0,1}。

注：1.本题非原创，见戳他(修复中，先别点)
2.答案：见【最佳答案】处。

最佳战士：dolly_yos2
奖励：10荣誉+6贡献（通过判定）
使用语言：C++

（第二题明天再说吧 ）
18：00前回答会有20鱼币额外奖励哦 （已结束）
18：31+10分钟（考虑到不可抗因素）前回答有10鱼币（已结束）
19：01前8鱼币（已结束）
19：31前5鱼币  (已结束）
20：00前3鱼币（结束）
20：31前1鱼币（结束）
注：此活动仅限一人，若一人回答对，剩下的直接作废


https://fishc.com.cn/thread-223717-1-1.html
鱼币福利！
保底2鱼币活动开始！
万水千山总是情，给个评分行不行

最佳答案

月排行榜 / 总排行榜

dolly_yos2

2023-1-29 12:20:58

感觉好像有点思路，试着写了一个

1. #include <stdio.h>
   
2. #include <stdint.h>
   
3. #include <stdbool.h>
   
4. const uint64_t mod = 1000000007;
   
5. struct edge{
   
6.     int64_t weight;
   
7.     uint32_t destination;
   
8.     uint32_t next;
   
9. };
   
10. struct edge edges[(unsigned int)4e5];
    
11. uint32_t head[(unsigned int)2e5 + 1];
    
12. uint32_t next_edge;
    
13. uint32_t n;
    
14. int64_t l, r;
    
15. void insert_edge(uint32_t source, uint32_t destination, int64_t weight){
    
16.     edges[next_edge].weight = weight;
    
17.     edges[next_edge].destination = destination;
    
18.     edges[next_edge].next = head[source];
    
19.     head[source] = next_edge++;
    
20. }
    
21. void trace(
    
22.     uint32_t target,
    
23.     int64_t p_weight, int64_t p_low, int64_t p_high,
    
24.     int64_t* c_low, int64_t* c_high
    
25. ){
    
26.     uint32_t start = head[target];
    
27.     int64_t low = p_weight - p_high;
    
28.     int64_t high = p_weight - p_low;
    
29.     head[target] |= 1 << 31;
    
30.     int64_t child_low, child_high;
    
31.     for(uint32_t edge = start; edge != 0x7fffffff; edge = edges[edge].next){
    
32.         if(head[edges[edge].destination] >> 31 == 1) continue;
    
33.         if(edges[edge].weight - low < l || edges[edge].weight - high > r){
    
34.             low = 1;
    
35.             high = 0;
    
36.             break;
    
37.         }
    
38.         if(edges[edge].weight - r > low) low = edges[edge].weight - r;
    
39.         if(edges[edge].weight - l < high) high = edges[edge].weight - l;
    
40.         trace(edges[edge].destination, edges[edge].weight, low, high, &child_low, &child_high);
    
41.         if(child_low > child_high){
    
42.             low = 1;
    
43.             high = 0;
    
44.             break;
    
45.         }
    
46.         if(edges[edge].weight - child_high > low) low = edges[edge].weight - child_high;
    
47.         if(edges[edge].weight - child_low < high) high = edges[edge].weight - child_low;
    
48.     }
    
49.     *c_low = low;
    
50.     *c_high = high;
    
51. }
    
52. void group_main(){
    
53.     uint64_t result = 1;
    
54.     scanf("%u%ld%ld", &n, &l, &r);
    
55.     int64_t minimum_weight = l + l;
    
56.     int64_t maximum_weight = r + r;
    
57.     for(uint32_t i = 1; i <= n; i++) head[i] = 0x7fffffff;
    
58.     next_edge = 0;
    
59.     uint8_t op;
    
60.     uint32_t source, destination;
    
61.     int64_t weight;
    
62.     for(uint32_t i = 1; i < n; i++){
    
63.         scanf("%hhu", &op);
    
64.         if(op == 0) scanf("%*u%*u");
    
65.         else if(op == 1){
    
66.             scanf("%u%u%ld", &source, &destination, &weight);
    
67.             if(weight > maximum_weight || weight < minimum_weight){
    
68.                 printf("0\n");
    
69.                 return;
    
70.             }
    
71.             insert_edge(source, destination, weight);
    
72.             insert_edge(destination, source, weight);
    
73.         }
    
74.     }
    
75.     int64_t left, right;
    
76.     for(uint32_t i = 1; i <= n; i++){
    
77.         if(head[i] >> 31 == 0){
    
78.             trace(i, l + r, l, r, &left, &right);
    
79.             if(left > right){
    
80.                 result = 0;
    
81.                 break;
    
82.             }
    
83.             result = ((right - left + 1) * result) % mod;
    
84.             if(result == 0) break;
    
85.         }
    
86.     }
    
87.     printf("%lu\n", result);
    
88. }
    
89. int main(){
    
90.     uint8_t T;
    
91.     scanf("%hhu", &T);
    
92.     for(uint8_t i = 0; i < T; i++) group_main();
    
93.     return 0;
    
94. }

复制代码

跳转到最佳答案楼层

sfqxx

zhangjinxuan 发表于 2023-2-1 23:18
绿题

应该给你们选一个黑题

sfqxx

元豪 发表于 2023-1-28 13:03
我去！还真的瞎选啊！

我甚至怀疑这题高达 提高+/省选-

是普及/提高_

sfqxx

zhangjinxuan 发表于 2023-1-27 21:31
是因为你是瞎选的题，啊呵呵，我说随便选你还真的就随便选啊

sfqxx

真6

zhangjinxuan

元豪 发表于 2023-1-28 13:03
我去！还真的瞎选啊！

我甚至怀疑这题高达 提高+/省选-

绿题

sfqxx

dolly_yos2 发表于 2023-1-29 14:26
有点不可思议
我的整体思路是这样的：
所有无权边可以忽略，这会将这棵树切分成一组所有边都是有权边的 ...

看看第2行，他说太短
我要下了

dolly_yos2

sfqxx 发表于 2023-1-29 13:28
拿着您的代码试了一下，得分85
有2个文件是WA
看看能不能改，不过这样已经很厉害了

有点不可思议
我的整体思路是这样的：
所有无权边可以忽略，这会将这棵树切分成一组所有边都是有权边的树（一个森林）
这个森林中的每一棵树中只要确定了任何一个点的取值，这棵树中所有点的取值就都确定了；任何一个点上的值变化，整棵树上的所有点的值一定一同发生变化，因此一棵树上点的填法数量和其中任何一个点的可取值数量是一致的
求出森林中每棵树的不同填法数量，将这些数量乘在一起就应该得到所有不同填法的数量
我又重新看了一遍我的代码，一共会调用 T 次 group_main，而 group_main 有且仅有两个出口，分别是第 69 行的 return 和函数结尾，两处都必然会经过一个 printf 函数输出当前组的结果，除非程序出现异常否则不应该缺少某组的输出。然而若程序出现异常，那么评测机的反馈理应为 RE 等异常退出状态而不是 WA
另一个问题期望答案应该是 7。考虑这一子任务的规模， n 不超过 10 而 l 和 r 均不小于 0 且不大于 5。可能性最多的情况是完全无约束的、最大点数量、最大取值范围，即全部边无权值、n 为 10 且 l, r 分别为 0 和 5。这一情况下每一个点各自独立有 6 种不同的取值，总填法数应该是 6^10 即 60466176，这一值远小于 1e9+7，因此应该是取模前的结果就是 7。然而 7 是质数，也就是说为组成此答案应该有一组（森林中的一棵树）恰有 7 种填法而其他树（若存在）都仅有一种。然而在数据规模约束下任何点都不会有超过 6 种填法，很好奇我的思考哪里出现了疏漏，究竟是什么样的数据能够得到这个 7 种填法

sfqxx

dolly_yos2 发表于 2023-1-29 13:36
离谱 还能有全错在规模最小的数据上的情况
不过这大概说明思路是没有大问题的

dolly_yos2

sfqxx 发表于 2023-1-29 13:28
拿着您的代码试了一下，得分85
有2个文件是WA
看看能不能改，不过这样已经很厉害了

离谱 还能有全错在规模最小的数据上的情况
不过这大概说明思路是没有大问题的

sfqxx

dolly_yos2 发表于 2023-1-29 12:20
感觉好像有点思路，试着写了一个

拿着您的代码试了一下，得分85
有2个文件是WA
看看能不能改，不过这样已经很厉害了
测试信息：

基本看了一下，第一个文件错误原因是第二行太短，第二个文件错误答案。错误答案在第2行第1列，读8，应为7。

dolly_yos2

感觉好像有点思路，试着写了一个

1. #include <stdio.h>
   
2. #include <stdint.h>
   
3. #include <stdbool.h>
   
4. const uint64_t mod = 1000000007;
   
5. struct edge{
   
6.     int64_t weight;
   
7.     uint32_t destination;
   
8.     uint32_t next;
   
9. };
   
10. struct edge edges[(unsigned int)4e5];
    
11. uint32_t head[(unsigned int)2e5 + 1];
    
12. uint32_t next_edge;
    
13. uint32_t n;
    
14. int64_t l, r;
    
15. void insert_edge(uint32_t source, uint32_t destination, int64_t weight){
    
16.     edges[next_edge].weight = weight;
    
17.     edges[next_edge].destination = destination;
    
18.     edges[next_edge].next = head[source];
    
19.     head[source] = next_edge++;
    
20. }
    
21. void trace(
    
22.     uint32_t target,
    
23.     int64_t p_weight, int64_t p_low, int64_t p_high,
    
24.     int64_t* c_low, int64_t* c_high
    
25. ){
    
26.     uint32_t start = head[target];
    
27.     int64_t low = p_weight - p_high;
    
28.     int64_t high = p_weight - p_low;
    
29.     head[target] |= 1 << 31;
    
30.     int64_t child_low, child_high;
    
31.     for(uint32_t edge = start; edge != 0x7fffffff; edge = edges[edge].next){
    
32.         if(head[edges[edge].destination] >> 31 == 1) continue;
    
33.         if(edges[edge].weight - low < l || edges[edge].weight - high > r){
    
34.             low = 1;
    
35.             high = 0;
    
36.             break;
    
37.         }
    
38.         if(edges[edge].weight - r > low) low = edges[edge].weight - r;
    
39.         if(edges[edge].weight - l < high) high = edges[edge].weight - l;
    
40.         trace(edges[edge].destination, edges[edge].weight, low, high, &child_low, &child_high);
    
41.         if(child_low > child_high){
    
42.             low = 1;
    
43.             high = 0;
    
44.             break;
    
45.         }
    
46.         if(edges[edge].weight - child_high > low) low = edges[edge].weight - child_high;
    
47.         if(edges[edge].weight - child_low < high) high = edges[edge].weight - child_low;
    
48.     }
    
49.     *c_low = low;
    
50.     *c_high = high;
    
51. }
    
52. void group_main(){
    
53.     uint64_t result = 1;
    
54.     scanf("%u%ld%ld", &n, &l, &r);
    
55.     int64_t minimum_weight = l + l;
    
56.     int64_t maximum_weight = r + r;
    
57.     for(uint32_t i = 1; i <= n; i++) head[i] = 0x7fffffff;
    
58.     next_edge = 0;
    
59.     uint8_t op;
    
60.     uint32_t source, destination;
    
61.     int64_t weight;
    
62.     for(uint32_t i = 1; i < n; i++){
    
63.         scanf("%hhu", &op);
    
64.         if(op == 0) scanf("%*u%*u");
    
65.         else if(op == 1){
    
66.             scanf("%u%u%ld", &source, &destination, &weight);
    
67.             if(weight > maximum_weight || weight < minimum_weight){
    
68.                 printf("0\n");
    
69.                 return;
    
70.             }
    
71.             insert_edge(source, destination, weight);
    
72.             insert_edge(destination, source, weight);
    
73.         }
    
74.     }
    
75.     int64_t left, right;
    
76.     for(uint32_t i = 1; i <= n; i++){
    
77.         if(head[i] >> 31 == 0){
    
78.             trace(i, l + r, l, r, &left, &right);
    
79.             if(left > right){
    
80.                 result = 0;
    
81.                 break;
    
82.             }
    
83.             result = ((right - left + 1) * result) % mod;
    
84.             if(result == 0) break;
    
85.         }
    
86.     }
    
87.     printf("%lu\n", result);
    
88. }
    
89. int main(){
    
90.     uint8_t T;
    
91.     scanf("%hhu", &T);
    
92.     for(uint8_t i = 0; i < T; i++) group_main();
    
93.     return 0;
    
94. }

复制代码

sfqxx

dolly_yos2 发表于 2023-1-29 11:47
想知道您怎么判断一个回答是不是正确
比如您有一些输入和对应的答案吗？这道题目没有找到出处，您是否有 ...

有，不知道现在能不能再提交
有测试的

dolly_yos2

sfqxx 发表于 2023-1-29 11:41
？没理解

想知道您怎么判断一个回答是不是正确
比如您有一些输入和对应的答案吗？这道题目没有找到出处，您是否有对程序进行测试的途径？

sfqxx

dolly_yos2 发表于 2023-1-29 11:08
好奇一下这道题您有测试数据吗？

？没理解

dolly_yos2

好奇一下这道题您有测试数据吗？

sfqxx

元豪 发表于 2023-1-28 13:03
我去！还真的瞎选啊！

我甚至怀疑这题高达 提高+/省选-

今天选简单一些

元豪

sfqxx 发表于 2023-1-27 22:21
我***什么时候说原创了

我去！还真的瞎选啊！

我甚至怀疑这题高达 提高+/省选-

hziyan

hziyan 发表于 2023-1-28 12:34
。。何止有点难，逻辑判断部分我目前只有一种暴力穷举，我相信大部分人倒在这个地方了

不整了，再整伤身，我今天忙，忙完先(今天可能一整天都忙）再看看吧

sfqxx

hziyan 发表于 2023-1-28 12:34
。。何止有点难，逻辑判断部分我目前只有一种暴力穷举，我相信大部分人倒在这个地方了

我去看看现在的情况