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

· · 题解

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