当前位置：首页 > news >正文

打卡信奥刷题（3291）用C++实现信奥题 P8971 『GROI-R1』虹色的彼岸花

news 2026/5/25 14:18:00

P8971 『GROI-R1』虹色的彼岸花

题目背景

少年身着春季校服的深灰色外套与黑色短裤，外套内是白净的衬衫。

他的右手不知为何缠着绷带，右眼用头发挡得严严实实，扑面而来的是一种神秘感。

一瓣鲜红的彼岸花，在教室上空无人在意之处打旋。

玘的身世，总是一个谜题吧。

「所以你到底是什么人，又为什么要来这里！」

可是彼岸花显然不想让你知道这些。

题目描述

玘给了寒一棵编号为1∼n1\sim n1∼n的树，这棵树上每个点都有一个点权，同时有些边有边权，有些边没有边权。可是玘把每一个点的点权删除了。寒只知道点权都是整数，而且在lll和rrr之间（包含端点）。而且，点权和边权有着下面的特殊关系：

对于有边权的边，要求连接的两个点的点权和为边权。
对于没有边权的边，无限制。

玘问寒这棵树有多少种不同的点权填写方式。两种填写方式不同，当且仅当至少存在一个点的点权不同。可是寒不会做这个题。

寒请你解决这个问题。

输入格式

本题有多组测试数据。

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

对于每一组测试数据：

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

5 6480

说明/提示

样例解释

对于样例的第一组测试数据，可以得到下图：

555种填写方式分别为：

{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}\{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\}{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}

可以证明，不存在别的填写方式。

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

数据范围

本题采用捆绑测试。

子任务编号	数据范围	特殊性质	分值
Subtask1\text{Subtask1}Subtask1	1≤n≤101\le n\le 101≤n≤10，0≤l,r≤50\le l,r\le50≤l,r≤5	151515
Subtask2\text{Subtask2}Subtask2	1≤n≤2×1051\le n\le 2\times 10^51≤n≤2×105，0≤l,r≤50\le l,r\le50≤l,r≤5	202020
Subtask3\text{Subtask3}Subtask3	1≤n≤101\le n\le 101≤n≤10，−109≤l,r≤109-10^9\le l,r\le 10^9−109≤l,r≤109	151515
Subtask4\text{Subtask4}Subtask4	1≤n≤2×1051\le n\le 2\times10^51≤n≤2×105，−109≤l,r≤109-10^9\le l,r\le 10^9−109≤l,r≤109	有	101010
Subtask5\text{Subtask5}Subtask5	1≤n≤2×1051\le n\le 2\times10^51≤n≤2×105，−109≤l,r≤109-10^9\le l,r\le 10^9−109≤l,r≤109	404040

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

对于100%100\%100%的数据，保证1≤T≤51\le T \le 51≤T≤5，1≤n≤2×1051\le n\le 2\times10^51≤n≤2×105，1≤∑n≤1061\le \sum n\le 10^61≤∑n≤106，−109≤l≤r≤109-10^9\le l\le r \le 10^9−109≤l≤r≤109，−109≤w≤109-10^9\le w\le 10^9−109≤w≤109，op∈{0,1}op\in\{0,1\}op∈{0,1}。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+5,mod=1e9+7;structnode{intto,next,w;}e[N<<1];longlongl,r;longlongn,t,cnt,ans;longlongh[N];longlongll,rr,x,y,op,w;boolvis[N];voidLink(intx,inty,intw){e[++cnt].to=y;e[cnt].next=h[x];e[cnt].w=w;h[x]=cnt;}voiddfs(intx,intk,intsign){vis[x]=true;longlongnl=l-k,nr=r-k;//解不等式if(sign==-1)swap(nl,nr),nl=-nl,nr=-nr;ll=max(ll,nl),rr=min(rr,nr);//更新左极值、右极值for(inti=h[x];i;i=e[i].next){if(!vis[e[i].to])dfs(e[i].to,e[i].w-k,-sign);//计算k和sign}}intmain(){cin>>t;while(t--){cin>>n>>l>>r;memset(vis,false,sizeof(vis));//多测清空memset(e,0,sizeof(e));memset(h,0,sizeof(h));cnt=0;ans=1;for(inti=1;i<=n-1;i++){cin>>op>>x>>y;if(op==1)cin>>w;elsecontinue;//忽略无边权的边Link(x,y,w);Link(y,x,w);}for(inti=1;i<=n;i++){ll=l,rr=r;if(!vis[i]){dfs(i,0,1);//从自己开始，自己的k是0，sign是1if(rr<ll)ans*=0;//更新范围elseans=ans*(rr-ll+1)%mod;}}cout<<ans<<endl;}return0;}