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

CASCwty · 2025-09-19 13:42:49 · 题解

思路

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

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

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

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

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

设点 u 的点权为 p(u)，一条连接 u 和 v 的边边权为 w(u,v)。

则有：

我们设 p(u) 的取值范围是 [mn_u,mx_u]

则有：

根据这个，我们只需先钦定以 x 为根的树 mx_x=r,mn_x=l。这样递推下去，最后根据儿子节点的取值反推根节点取值，就可以确定有多少个解了。

最后注意一下边界条件的判断，一定要在 [l,r] 范围内。

代码

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

#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;
} 

警示后人

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