自动搬运

查看原文

来自洛谷，原作者为

	zSqr_Mahiro_Oyama 自宅一级警备员 || 你凭什么定义我的性别

搬运于2025-08-24 22:44:12，当前版本为作者最后更新于2024-08-14 16:47:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

题目传送门

分析部分：

对于一条边连接的两个点，如果这条边有边权，当其中一个点的点权确定时，另一个点的点权也会确定；如果这条边无边权，两个点的点权相互之间不会有影响。因此可以将无边权的边忽略，将这一棵树看作森林，对其中的每棵树进行处理。

对于一棵树，只要确定了一个点的点权，就可以确定通过边权计算出其他点的点权。因此我们可以从一点开始访问，令其值为 $x$，将其他点的点权用 $x$ 和 一个数 $k$ 来表示。对于一个点来说，点权只会有 $k+x$ 和 $k-x$ 这两种情况。因此我们需要计算 $k$ 和判断 $x$ 的正负性。

我们可以从最开始的点进行 dfs。对于一个点 $u$，设它的点权为 $k_u+sign_u \times x$，则它的儿子 $v$ 的点权就是 $w_{u,v}-(k_u+sign_u \times x)=w_{u,v}-k_u-sign_u \times x$，可以得到 $k_v=w_{u,v}-k_u$，$sign_v=-sign_u$，实际实现时只需将 $k$ 和 $sign$ 作为参数下传即可。对于算出的点权，解出关于 $x$ 的不等式，取左极值最大，右极值最小。设最终计算出的解集为 $ll \le x \le rr$ （一年半前极差的取名习惯），若 $rr<ll$ ，说明没有可行解，否则这棵树的填写方式共有 $rr-ll+1$ 种，将每棵树的填写方式相乘即可。

代码部分：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,mod=1e9+7;
struct node{
	int to,next,w;
}e[N<<1];
long long l,r;
long long n,t,cnt,ans;
long long h[N];
long long ll,rr,x,y,op,w;
bool vis[N];
void Link(int x,int y,int w){
	e[++cnt].to=y;
	e[cnt].next=h[x];
	e[cnt].w=w;
	h[x]=cnt;
}
void dfs(int x,int k,int sign){
	vis[x]=true;
	long long nl=l-k,nr=r-k;//解不等式
	if(sign==-1)swap(nl,nr),nl=-nl,nr=-nr;
	ll=max(ll,nl),rr=min(rr,nr);//更新左极值、右极值
	for(int i=h[x];i;i=e[i].next){
		if(!vis[e[i].to])
			dfs(e[i].to,e[i].w-k,-sign);//计算k和sign
	}
}
int main(){
	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(int i=1;i<=n-1;i++){
			cin>>op>>x>>y;
			if(op==1)cin>>w;
			else continue;//忽略无边权的边
			Link(x,y,w);
			Link(y,x,w);
		}
		for(int i=1;i<=n;i++){
			ll=l,rr=r;
			if(!vis[i]){
				dfs(i,0,1);//从自己开始，自己的k是0，sign是1
				if(rr<ll)ans*=0;//更新范围
				else ans=ans*(rr-ll+1)%mod;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}