#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
//ifstream cin("minmaxtree.in");
//ofstream cout("minmaxtree.out");
int t[70005],euclid[200005],niv[200005],cnt,put[20],lg[200005],rmq[20][200005],fr[200005],tata[200005],tatac[200005],ap[200005],maxim[200005],minim[200005],cod[200005],viz[70005],st[70005],dr[70005];
vector<int> temp[70005],v[70005];
vector<int> graf[70005];
struct query{
int a,b,c;
}mi[70005],ma[70005];
void dfs(int nod,int h){
t[nod]=1;
euclid[++cnt]=nod;
niv[cnt]=h;
for(auto u:temp[nod]){
if(t[u]==1)
continue;
v[nod].push_back(u);
tata[u]=nod;
tatac[u]=nod;
dfs(u,h+1);
euclid[++cnt]=nod;
niv[cnt]=h;
}
}
void add(int a,int b){
graf[a].push_back(b);
}
int maa(int a,int b){
if(niv[a]>niv[b]){
return b;
}
return a;
}
int lca(int st,int dr){
int dist=dr-st+1;
int e=lg[dist];
return euclid[maa(rmq[e][st],rmq[e][dr-put[e]+1])];
}
int find_lca(int a,int b){
a=fr[a];
b=fr[b];
if(a>b)
swap(a,b);
return lca(a,b);
}
bool misort(query a,query b){
return a.c<b.c;
}
bool masort(query a,query b){
return a.c>b.c;
}
int mai_jos(int a,int b){
if(niv[fr[a]]>niv[fr[b]])
return true;
return false;
}
void update(int jos,int sus,int val,bool ok){
int cur=jos;
while(mai_jos(cur,sus)==true){
cur=tata[cur];
}
int nex=cur;
cur=jos;
while(mai_jos(cur,sus)==true){
int aux=tata[cur];
tata[cur]=nex;
if(ap[cod[cur]]==0){
if(ok==0)
maxim[cod[cur]]=val;
else
minim[cod[cur]]=val;
ap[cod[cur]]=1;
}
cur=aux;
}
}
bool cup(int w){
if(viz[w]==1)
return 0;
viz[w]=1;
for(auto u:graf[w]){
if(dr[u]==0){
st[w]=u;
dr[u]=w;
return 1;
}
}
for(auto u:graf[w]){
if(cup(dr[u])==1){
st[w]=u;
dr[u]=w;
return 1;
}
}
return 0;
}
pair<int,int> muchie[70005];
int main()
{
int n,a,b,k,c,c1=0,c2=0;
char ch;
cin>>n;
for(int i=1;i<n;i++){
cin>>a>>b;
temp[a].push_back(b);
temp[b].push_back(a);
}
dfs(1,1);
for(int i=cnt;i>=1;i--){
fr[euclid[i]]=i;
}
for(int i=1;i<=cnt;i++){
rmq[0][i]=i;
}
for(int i=1;i<=17;i++){
put[i]=put[i-1]*2;
lg[put[i]]++;
}
for(int i=1;i<=100000;i++){
lg[i]+=lg[i-1];
}
for(int i=1;i<=17;i++){
for(int j=1;j<=cnt;j++){
if(j+put[i]>cnt)
break;
rmq[i][j]=maa(rmq[i-1][j],rmq[i-1][j+put[i-1]]);
}
}
cin>>k;
cin.get();
for(int i=1;i<=k;i++){
cin>>ch>>a>>b>>c;
cin.get();
if(ch=='m'){
mi[++c1].a=a;
mi[c1].b=b;
mi[c1].c=c;
}
else{
ma[++c2].a=a;
ma[c2].b=b;
ma[c2].c=c;
}
}
sort(mi+1,mi+c1+1,misort);
sort(ma+1,ma+c2+1,masort);
for(int i=1;i<=n;i++){
maxim[i]=-1;
minim[i]=-1;
}
//for(int i=1;i<=n;i++)
//cout<<tata[i]<<" ";
//cout<<"\n";
int contor=0;
for(int i=2;i<=n;i++){
cod[i]=++contor;
muchie[contor]=make_pair(i,tata[i]);
}
for(int i=1;i<=c1;i++){
//cout<<i<<"\n";
int lca=find_lca(mi[i].a,mi[i].b);
//cout<<lca<<" ";
update(mi[i].a,lca,mi[i].c,1);
update(mi[i].b,lca,mi[i].c,1);
int a=mi[i].a,b=mi[i].b;
while(a!=lca){
graf[cod[a]].push_back(i);
a=tatac[a];
}
while(b!=lca){
graf[cod[b]].push_back(i);
b=tatac[b];
}
}
for(int i=1;i<=n;i++){
ap[i]=0;
tata[i]=tatac[i];
}
for(int i=1;i<=c2;i++){
int lca=find_lca(ma[i].a,ma[i].b);
update(ma[i].a,lca,ma[i].c,0);
update(ma[i].b,lca,ma[i].c,0);
int a=ma[i].a,b=ma[i].b;
while(a!=lca){
graf[cod[a]].push_back(i+c1);
a=tatac[a];
}
while(b!=lca){
graf[cod[b]].push_back(i+c1);
b=tatac[b];
}
}
//for(int i=1;i<n;i++){
//cout<<i<<"->";
//for(auto u:graf[i]){
//if(u<=c1){
//cout<<mi[u].c<<" "<<u<<" ";
//}
//else{
//cout<<ma[u-c1].c<<" "<<u<<" ";
//}
//}
//cout<<"\n";
//}
//for(int i=1;i<n;i++){
//cout<<i<<" "<<maxim[i]<<" "<<minim[i]<<"\n";
//}
int co=0,pco;
do{
pco=co;
for(int i=1;i<n;i++){
viz[i]=0;
}
for(int i=1;i<n;i++){
if(st[i]==0){
co+=cup(i);
}
}
}while(co!=pco);
//cout<<"\n\n";
for(int i=1;i<n;i++){
cout<<muchie[i].first<<" "<<muchie[i].second<<" ";
if(st[i]!=0){
//cout<<i<<" ";
if(st[i]<=c1){
cout<<mi[st[i]].c<<"\n";
}
else{
cout<<ma[st[i]-c1].c<<"\n";
}
}
else{
if(maxim[i]!=-1){
cout<<maxim[i]<<"\n";
continue;
}
if(minim[i]!=-1){
cout<<minim[i]<<"\n";
continue;
}
cout<<2<<"\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
520 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
678 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
628 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
520 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
