#include<bits/stdc++.h>
using namespace std;
#define int long long
struct bip_graph{
vector<vector<int> > adi;
vector<int> m;
vector<bool> vis;
bip_graph(int n, int k){
adi.resize(n);
m.resize(k, -1);
vis.resize(n, false);
}
bool improve_matching(int v){
if(vis[v]) return false;
vis[v]=true;
for(auto u: adi[v]){
if(m[u]==-1 || improve_matching(m[u])){
m[u]=v;
return true;
}
}
return false;
}
void matching(int n){
vector<bool> done(n);
for(auto e: m){
if(e!=-1) done[e]=true;
}
vis.assign(n, false);
for(int i=0; i<n; i++){
if(!done[i] && improve_matching(i)){
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());
int ind=lower.second;
ans[v]=lower.first;
g.adi[ind].push_back(v);
if(!g.vis[ind]){
g.m[v]=ind;
g.vis[ind]=true;
}
}
if(!ub.empty()){
auto upper=*ub.begin();
int ind=upper.second;
g.adi[ind].push_back(v);
if(!g.vis[ind] && g.m[v]==-1){
g.m[v]=ind;
g.vis[ind]=true;
}
}
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<n; i++){
if(g.m[i]!=-1){
ans[i]=val[g.m[i]];
}
}
for(int i=1; i<n; i++){
cout << i+1 << " " << t.up[i][0]+1 << " " << ans[i] << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
257 ms |
50308 KB |
Output is correct |
| 2 |
Correct |
237 ms |
36808 KB |
Output is correct |
| 3 |
Execution timed out |
1091 ms |
42204 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
30408 KB |
Output is correct |
| 2 |
Correct |
139 ms |
31072 KB |
Output is correct |
| 3 |
Correct |
174 ms |
44024 KB |
Output is correct |
| 4 |
Correct |
199 ms |
50520 KB |
Output is correct |
| 5 |
Correct |
149 ms |
34072 KB |
Output is correct |
| 6 |
Correct |
147 ms |
35996 KB |
Output is correct |
| 7 |
Correct |
134 ms |
31608 KB |
Output is correct |
| 8 |
Correct |
148 ms |
31504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
257 ms |
50308 KB |
Output is correct |
| 6 |
Correct |
237 ms |
36808 KB |
Output is correct |
| 7 |
Execution timed out |
1091 ms |
42204 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
