#include<bits/stdc++.h>
using namespace std;
#define int long long
struct bip_graph{
vector<vector<int> > adi;
vector<int> m;
bip_graph(int n, int k){
adi.resize(n);
m.resize(k, -1);
}
bool improve_matching(int v, vector<bool>& vis){
if(vis[v]) return false;
vis[v]=true;
for(auto u: adi[v]){
if(m[u]==-1 || improve_matching(m[u], vis)){
m[u]=v;
return true;
}
}
return false;
}
void matching(int n){
vector<bool> vis(n, false);
for(int i=0; i<n; i++){
if(improve_matching(i, vis)){
vis.assign(n, false);
}
}
}
};
struct tree{
const int l=25;
vector<vector<int> > adi;
int t=0;
vector<int> tin;
vector<int> tout;
vector<vector<int> > up;
vector<vector<pair<int,int> > > mmax;
vector<vector<pair<int,int> > > mmin;
tree(int n){
adi.resize(n);
tin.resize(n);
tout.resize(n);
up.resize(n, vector<int> (l, -1));
mmax.resize(n);
mmin.resize(n);
}
void dfs_prepare(int v, int p){
tin[v]=t; t++;
up[v][0]=p;
for(int i=1; i<l; i++){
if(up[v][i-1]!=-1){
up[v][i]=up[up[v][i-1]][i-1];
}
}
for(auto u: adi[v]){
if(u==p) continue;
dfs_prepare(u, v);
}
tout[v]=t; t++;
}
bool is_ancestor(int a, int b){
return tin[a]<=tin[b] && tout[b]<=tout[a];
}
int lca(int a, int b){
if(is_ancestor(a, b)) return a;
if(is_ancestor(b, a)) return b;
for(int i=l-1; i>=0; i--){
if(up[a][i]!=-1 && !is_ancestor(up[a][i], b)){
a=up[a][i];
}
}
return up[a][0];
}
pair<set<pair<int,int> >, set<pair<int,int> > > dfs(int v, int p, bip_graph& g,
vector<int>& ans){
set<pair<int,int> > lb;
set<pair<int,int> > ub;
for(auto u: adi[v]){
if(u==p) continue;
auto [l, r]=dfs(u, v, g, ans);
if(l.size()>lb.size()) swap(l, lb);
for(auto e: l) lb.insert(e);
if(r.size()>ub.size()) swap(r, ub);
for(auto e: r) ub.insert(e);
}
for(auto e: mmin[v]){
if(e.second>0){
lb.erase(e);
}
else{
e.second=-e.second;
lb.insert(e);
}
}
for(auto e: mmax[v]){
if(e.second>0){
ub.erase(e);
}
else{
e.second=-e.second;
ub.insert(e);
}
}
if(!lb.empty()){
auto lower=*prev(lb.end());
ans[v]=lower.first;
g.adi[lower.second].push_back(v);
}
if(!ub.empty()){
auto upper=*ub.begin();
g.adi[upper.second].push_back(v);
}
return {lb, ub};
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
tree t(n);
for(int i=0; i<n-1; i++){
int a, b;
cin >> a >> b;
a--; b--;
t.adi[a].push_back(b);
t.adi[b].push_back(a);
}
t.dfs_prepare(0, -1);
int k;
cin >> k;
vector<int> val(k+1);
for(int i=1; i<=k; i++){
char x;
cin >> x;
int a, b, c;
cin >> a >> b >> c;
a--; b--;
int l=t.lca(a, b);
val[i]=c;
if(x=='M'){
t.mmax[a].push_back({c, -i});
t.mmax[b].push_back({c, -i});
t.mmax[l].push_back({c, i});
}
else{
t.mmin[a].push_back({c, -i});
t.mmin[b].push_back({c, -i});
t.mmin[l].push_back({c, i});
}
}
bip_graph g(k+1, n);
vector<int> ans(n, -1);
t.dfs(0, -1, g, ans);
g.matching(k+1);
for(int i=1; i<=k; i++){
assert(g.m[i]!=-1);
ans[g.m[i]]=val[i];
}
for(int i=1; i<n; i++){
cout << i+1 << " " << t.up[i][0]+1 << " " << ans[i] << "\n";
}
}
Compilation message
minmaxtree.cpp: In member function 'std::pair<std::set<std::pair<long long int, long long int> >, std::set<std::pair<long long int, long long int> > > tree::dfs(long long int, long long int, bip_graph&, std::vector<long long int>&)':
minmaxtree.cpp:100:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
100 | auto [l, r]=dfs(u, v, g, ans);
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
274 ms |
98692 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
130 ms |
58940 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
