|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
×
本帖最后由 sfqxx 于 2025-7-2 15:52 编辑
你们顺着藏宝图的方向，走到了一个藏有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 取模。
输入与输出样例
输入：
- 2
- 6 0 4
- 1 1 2 2
- 1 2 3 4
- 1 3 4 2
- 0 2 5
- 1 4 6 3
- 6 -1 4
- 1 1 2 4
- 0 2 3
- 0 3 4
- 0 2 5
- 0 4 6
输出：
说明/提示
样例解释
对于样例的第一组测试数据，可以得到下图：
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鱼币活动开始！
万水千山总是情，给个评分行不行
|
评分
-
查看全部评分
|
狗仔卡
发表于 2023-1-27 16:21:33
置顶卡
千斤顶
显身卡
发表于 2023-1-27 17:02:39
不整了，再整伤身，我今天忙，忙完先(今天可能一整天都忙）再看看吧