Berland Beauty

F - Berland Beauty

因为这道题的 n 只有5000的范围，所以直接暴力用\(O(n^2)\)的写法也是可以的，只需要先 dfs 一遍，把每一条边都赋为其可能达到的最大值，然后再把所有的数据再 check 一遍即可。当然这道题也可以用树链剖分来进行优化。

// Created by CAD on 2020/2/7.
#include <bits/stdc++.h>

#define fi first
#define se second
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>
using namespace std;
const int maxn=5005;
int e[maxn];
piii q[maxn];
vector<pii> g[maxn];
bool dfs(int f,int s,int t,int c){
    if(s==t) return 1;
    bool bj=0;
    for(auto i:g[s]){
        int v=i.fi;
        if(v!=f) if(dfs(s,v,t,c)) e[i.se]=max(e[i.se],c),bj=1;
    }
    return bj;
}
bool check(int f,int s,int t,int &ans){
    if(s==t) return 1;
    bool bj=0;
    for(auto i:g[s]){
        int v=i.fi;
        if(v!=f) if(check(s,v,t,ans)) ans=min(ans,e[i.se]),bj=1;
    }
    return bj;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n;  cin>>n;
    for(int i=1;i<=n-1;++i){
        int u,v;    cin>>u>>v;
        g[u].push_back({v,i}),g[v].push_back({u,i});
    }
    int Q;  cin>>Q;
    for(int i=1;i<=Q;++i){
        int a,b,c;cin>>a>>b>>c;
        q[i]={{a,b},c};
        dfs(0,a,b,c);
    }
    for(int i=1;i<=Q;++i){
        int ans=inf;
        check(0,q[i].fi.fi,q[i].fi.se,ans);
        if(ans!=q[i].se) return puts("-1");
    }
    for(int i=1;i<=n-1;++i)
        if(e[i]) cout<<e[i]<<" ";
        else cout<<1<<" ";
}

Berland Beauty

原文：https://www.cnblogs.com/CADCADCAD/p/12274166.html