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行每行先输入一个整数opopopop0op0op0表示这条边没有边权op1op1op1表示这条边有边权。如果op0op0op0再输入两个整数u,vu,vu,v表示这条边连接u,vu,vu,v两个点。如果op1op1op1再输入三个整数u,v,wu,v,wu,v,w表示有一条权值为www的边连接u,vu,vu,v两个点。输出格式对于每个测试点输出一行一个整数代表点权填写方式的个数。答案对109710^971097取模。输入输出样例 #1输入 #12 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输出 #15 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}Subtask11≤n≤101\le n\le 101≤n≤100≤l,r≤50\le l,r\le50≤l,r≤5151515Subtask2\text{Subtask2}Subtask21≤n≤2×1051\le n\le 2\times 10^51≤n≤2×1050≤l,r≤50\le l,r\le50≤l,r≤5202020Subtask3\text{Subtask3}Subtask31≤n≤101\le n\le 101≤n≤10−109≤l,r≤109-10^9\le l,r\le 10^9−109≤l,r≤109151515Subtask4\text{Subtask4}Subtask41≤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有101010Subtask5\text{Subtask5}Subtask51≤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≤109404040特殊性质保证每条边都无边权。对于100%100\%100%的数据保证1≤T≤51\le T \le 51≤T≤51≤n≤2×1051\le n\le 2\times10^51≤n≤2×1051≤∑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≤109op∈{0,1}op\in\{0,1\}op∈{0,1}。C实现#includebits/stdc.husingnamespacestd;constintN2e55,mod1e97;structnode{intto,next,w;}e[N1];longlongl,r;longlongn,t,cnt,ans;longlongh[N];longlongll,rr,x,y,op,w;boolvis[N];voidLink(intx,inty,intw){e[cnt].toy;e[cnt].nexth[x];e[cnt].ww;h[x]cnt;}voiddfs(intx,intk,intsign){vis[x]true;longlongnll-k,nrr-k;//解不等式if(sign-1)swap(nl,nr),nl-nl,nr-nr;llmax(ll,nl),rrmin(rr,nr);//更新左极值、右极值for(intih[x];i;ie[i].next){if(!vis[e[i].to])dfs(e[i].to,e[i].w-k,-sign);//计算k和sign}}intmain(){cint;while(t--){cinnlr;memset(vis,false,sizeof(vis));//多测清空memset(e,0,sizeof(e));memset(h,0,sizeof(h));cnt0;ans1;for(inti1;in-1;i){cinopxy;if(op1)cinw;elsecontinue;//忽略无边权的边Link(x,y,w);Link(y,x,w);}for(inti1;in;i){lll,rrr;if(!vis[i]){dfs(i,0,1);//从自己开始自己的k是0sign是1if(rrll)ans*0;//更新范围elseansans*(rr-ll1)%mod;}}coutansendl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
