题解：CF1296F Berland Beauty
__vector__
·
·
题解
Statement
给定了一棵 n 个点的树，每条边都有一个 1 \sim 10^6 之间的整数边权。
有 m 个条件，每个形式如下：
要求构造一组合法的边权满足所有条件。
### Solution
对于上述条件，首先满足 $a$ 到 $b$ 的路径上不能出现小于 $c$ 的边权。
在此基础上，每个边权应当尽可能小。
所以，为每条边赋一个初始边权 $1$，然后对于每对 $(a,b,c)$（含义见上述描述），将 $a$ 到 $b$ 路径上所有边权对 $c$ 取 max。
如果这个边权方案不符合要求，那么肯定不存在合法方案了。
```cpp
#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]);
}
}
```