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;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
