本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 15:49:00

Statement

给定了一棵 $n$ 个点的树，每条边都有一个 $1 \sim 10^6$ 之间的整数边权。

有 $m$ 个条件，每个形式如下：

• $a$ 点到 $b$ 点的路径上的最小边权是 $c$。

要求构造一组合法的边权满足所有条件。

$n,m \le 5000$。

Solution

对于上述条件，首先满足 $a$ 到 $b$ 的路径上不能出现小于 $c$ 的边权。

在此基础上，每个边权应当尽可能小。

所以，为每条边赋一个初始边权 $1$，然后对于每对 $(a,b,c)$（含义见上述描述），将 $a$ 到 $b$ 路径上所有边权对 $c$ 取 max。

如果这个边权方案不符合要求，那么肯定不存在合法方案了。

#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define mkpr make_pair
const int maxn=5005;
int n;
vector<pii> g[maxn];
int val[maxn];
int dep[maxn];
int fa[maxn];
int faid[maxn];
void dfs(int u,int _fa){
    fa[u]=_fa;
    dep[u]=dep[_fa]+1;
    for(auto [v,id]:g[u]){
        if(v==_fa)continue;
        faid[v]=id;
        dfs(v,u);
    }
}
vector<pair<int,int> > rem[maxn];
tuple<int,int,int> ops[maxn];
void solve(int id_of_test){
	read(n);
    FOR(i,1,n)val[i]=1;
    FOR(i,1,n-1){
        int x,y;
        read(x);
        read(y);
        g[x].eb(mkpr(y,i));
        g[y].eb(mkpr(x,i));
    }
    dfs(1,0);
    int m;
    read(m);
    FOR(i,1,m){
        int a,b,v;
        read(a);
        read(b);
        read(v);
        ops[i]=tie(a,b,v);
        vi path;
        while(a!=b){
            if(dep[a]<dep[b])swap(a,b);
            path.eb(faid[a]);
            a=fa[a];
        }
        for(int& eid:path)ckmx(val[eid],v);
    }
    FOR(i,1,m){
        int a,b,v;
        tie(a,b,v)=ops[i];
        vi path;
        while(a!=b){
            if(dep[a]<dep[b])swap(a,b);
            path.eb(faid[a]);
            a=fa[a];
        }
        bool yes=0;
        for(int& eid:path){
           \/\/ printf("i = %d meet = %d\n",i,val[v]);
            if(val[eid]<v){
                yes=0;
                break;
            }else if(val[eid]==v){
                yes=1;
            }
        }
        if(!yes){
            puts("-1");
            return;
        }
    }
    FOR(i,1,n-1){
        printf("%d ",val[i]);
    }
}