#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <utility>
#include <queue>
#include <string.h>
#include <map>
#define ii std::pair<int,int>
#define INF 1000000010
#define left(i) (i<<1)
#define right(i) ((i<<1)+1)
#define N 70100
typedef struct node{
int mx,mn;
}node;
node seg[N*4];
void build(){
for(int i = 0;i<N*4;i++)seg[i] = {INF,-1};
};
void update(int n, int l, int r, int a, int b, int v, int f){
if(l >= r)return;
if(l >= b || a >= r)return;
if(a <= l && r <= b){
if(f)seg[n].mx = std::min(seg[n].mx,v);
else seg[n].mn = std::max(seg[n].mn,v);
}else{
int m = (l+r)>>1;
update(right(n),m,r,a,b,v,f);
update(left(n),l,m,a,b,v,f);
};
};
int querry(int n, int l, int r, int x, int f){
if(l > x || r <= x)return f ? INF : -1;
if(l == x && l == r-1)return f ? seg[n].mx : seg[n].mn;
else{
int m = (l+r)>>1;
int vval;
if(x >= m){
vval = querry(right(n),m,r,x,f);
}else{
vval = querry(left(n),l,m,x,f);
};
return f ? std::min(seg[n].mx,vval) : std::max(seg[n].mn,vval);
};
};
int head[N];
std::vector<int> adj[N];
int ppar[N][20];
int in[N];
int out[N];
int cnt = 1;
std::map<int,std::vector<int>> mpp;
std::map<int,ii> rmp;
std::map<int,int> used;
ii tt[N];
int vv[N];
int n;
int dfs(int v,int p){
ppar[v][0] = p;
for(int i = 1;i<20;i++){
ppar[v][i] = ppar[ppar[v][i-1]][i-1];
};
int sz = 1;
int mx = 0;
int id = 0;
for(int i = 0;i<adj[v].size();i++){
if(adj[v][i] != p){
int ss = dfs(adj[v][i],v);
if(ss >mx){
mx = ss;
id = i;
};
sz += ss;
};
};
if(mx){
int tmp = adj[v][0];
adj[v][0] = adj[v][id];
adj[v][id] = tmp;
};
return sz;
};
void dff(int v, int p){
in[v] = cnt++;
rmp[in[v]-1] = {p,v};
for(int i = 0;i<adj[v].size();i++){
int nxt = adj[v][i];
if(nxt != p){
if(!i)head[nxt] = head[v];
dff(nxt,v);
};
};
out[v] = cnt++;
};
int before(int v, int u){
if(!u)return false;
if(!v)return true;
return in[v] < in[u] && out[v] > out[u];
};
int lca(int v, int u){
if(u == v)return v;
if(before(v,u))return v;
else if(before(u,v))return u;
for(int i = 19;i>=0;i--){
if(!before(ppar[v][i],u)){
v = ppar[v][i];
};
};
return ppar[v][0];
};
void upp(int s, int e, int v, int f){
int lc = lca(s,e);
if(lc != e){
upp(s,lc,v,f);
upp(e,lc,v,f);
};
while(s != e){
int tmp = head[s];
if(!before(tmp,e) && tmp != e){
update(1,0,n,in[tmp],in[s],v,f);
update(1,0,n,in[tmp]-1,in[tmp],v,f);
s = ppar[tmp][0];
}else{
//printf("hld: %d %d %d\n",s,e,tmp);
//printf("hld: %d %d %d\n",in[e],in[s],v);
update(1,0,n,in[e],in[s],v,f);
break;
};
};
};
int main(void){
head[1] = 1;
build();
int k;
scanf("%d",&n);
int x,y,z;
char str[2];
memset(vv,-1,sizeof(vv));
for(int i = 0;i<n-1;i++){
scanf("%d %d",&x,&y);
adj[x].push_back(y);
adj[y].push_back(x);
};
dfs(1,0);
dff(1,0);
scanf("%d",&k);
//printf("%d\n",k);
for(int i = 0;i<k;i++){
scanf("%s %d %d %d",str,&x,&y,&z);
if(str[0] == 'M'){
upp(x,y,z,1);
}else{
upp(x,y,z,0);
};
};
for(int i = 1;i<n;i++){
int mnn = querry(1,0,n,i,0);
int mxx = querry(1,0,n,i,1);
mpp[mnn].push_back(i);
mpp[mxx].push_back(i);
//printf("%d %d\n",mnn,mxx);
tt[i] = {mnn,mxx};
};
std::priority_queue<ii,std::vector<ii>,std::greater<ii>> pq;
for(auto &i : mpp){
if(i.first != INF && i.first != -1){
pq.push({i.second.size(),i.first});
used[i.first] = i.second.size();
//printf("geil: %d %d\n",i.first,i.second.size());
};
};
while(pq.size()){
ii akt = pq.top();pq.pop();
if(used[akt.second] == akt.first){
//printf("%d %d\n",akt.first,akt.second);
auto &vec = mpp[akt.second];
int id = 0;
while(true){
id = vec[vec.size()-1];
vec.pop_back();
if(vv[id] == -1){
vv[id] = akt.second;
break;
};
};
int mnn = tt[id].first;
int mxx = tt[id].second;
if(akt.second == mnn){
if(mxx != INF){
pq.push({--used[mxx],mxx});
};
}else{
if(mnn != -1){
pq.push({--used[mnn],mnn});
};
};
};
};
for(int i = 1;i<n;i++){
ii akt = rmp[i];
int cc = vv[i] != -1 ? vv[i] : tt[i].second;
printf("%d %d %d\n",akt.first,akt.second,cc);
};
return 0;
};
Compilation message
minmaxtree.cpp: In function 'int dfs(int, int)':
minmaxtree.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<adj[v].size();i++){
~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dff(int, int)':
minmaxtree.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<adj[v].size();i++){
~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
minmaxtree.cpp:155:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
minmaxtree.cpp:161:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&k);
~~~~~^~~~~~~~~
minmaxtree.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s %d %d %d",str,&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4472 KB |
Integer 0 violates the range [1, 20] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
213 ms |
26348 KB |
Integer 0 violates the range [1, 70000] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
137 ms |
38692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4472 KB |
Integer 0 violates the range [1, 20] |
| 2 |
Halted |
0 ms |
0 KB |
- |
