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

思路

首先我们可以得出一些结论：

对于边权为 $0$ 的边，显然的，所连接的两个节点取值是独立的。
根据上面结论，我们可以把这棵树直接搞成多个森林。
如果对于森林中的一棵树，我们钦定某个节点的值为 $x$ ，那么这棵树的其他节点值已经确定了。

第三个结论是个很重要的结论，因此，我们只需要找到某一个节点的权值取值范围，即可找到这棵树有多少个解。

答案即为所有树答案乘积。

那么，我们如何求一个点权值的取值范围？

设点

u

的点权为

p(u)

，一条连接

u

和

v

的边边权为

w(u,v)

。

则有：

p(u)+p(v)=w(u,v)

我们设

p(u)

的取值范围是

[mn_u,mx_u]

则有：

mn_u=l,mx_u=r

mx_v=w(u,v)-mn_u,mn_v=w(u,v)-mx_u

根据这个，我们只需先钦定以

x

为根的树

mx_x=r,mn_x=l

。这样递推下去，最后根据儿子节点的取值反推根节点取值，就可以确定有多少个解了。

最后注意一下边界条件的判断，一定要在

[l,r]

范围内。

代码

这种做法甚至跑得很快，只开 IOS 都可以跑到最优解第一页。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=2e5+5;
int T,n,op,u,v,vis[N];
ll l,r,mn[N],mx[N],w,ans;
struct node{int v;ll w;};
vector<node>G[N];
inline void init(int n){
	ans=0;
	for(int i(1);i<=n;++i){
		mn[i]=l,mx[i]=r;
		vis[i]=0;
		G[i].clear();
	}
}
void dfs(int u){
	for(auto t:G[u]){
		int v=t.v;
		ll w=t.w;
		if(vis[v])continue;
		vis[v]=1;
		mx[v]=min(w-mn[u],mx[v]);
		mn[v]=max(w-mx[u],mn[v]);
		dfs(v);
		mx[u]=min(w-mn[v],mx[u]);
		mn[u]=max(w-mx[v],mn[u]);
	}
}
inline void solve(){
	cin>>n>>l>>r;
	init(n),ans=1;
	for(int i(1);i<n;++i){
		cin>>op>>u>>v;
		if(op==1){
			cin>>w;
			G[u].push_back({v,w});
			G[v].push_back({u,w});
		}
	}
	for(int i(1);i<=n;++i){
		if(!vis[i]){
			vis[i]=1;
			mx[i]=r,mn[i]=l;
			dfs(i);
			ans=ans*(max(ll(0),mx[i]-mn[i]+1)%mod)%mod;
		}
	}
	cout<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	for(;T;--T){
		solve();
	}
	return 0;
}

警示后人

多测不清空，爆零两行泪。

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

文章操作

思路

代码

警示后人

相关推荐

评论

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