#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
vector<int> adj[77777];
int siz[77777];
int in[77777];
int h[77777];
int nxt[77777];
int out[77777];
int timer;
const int LG = 17;
int st[LG][77777];
void dfs_siz(int u, int p)
{
siz[u]=1;
if(adj[u][0]==p&&adj[u].size()>1)
{
swap(adj[u][0],adj[u][1]);
}
for(auto &v:adj[u])
{
if(v==p) continue;
dfs_siz(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[adj[u][0]])
{
swap(v,adj[u][0]);
}
}
}
int L[77777];
int R[77777];
const int INF = int(1e9)+8;
void dfs_hld(int u, int p)
{
in[u]=timer++; st[0][u]=p;
for(int v:adj[u])
{
if(v==p) continue;
nxt[v] = (v==adj[u][0]?nxt[u]:v);
h[v]=h[u]+1; L[v]=-INF; R[v]=INF;
dfs_hld(v,u);
}
out[u]=timer;
}
int ans[77777];
int go_up(int u, int k)
{
for(int i=LG-1;i>=0;i--)
{
//cerr<<u<<' '<<k<<' '<<i<<' '<<st[1][2]<<'\n';
if(k&(1<<i)) u=st[i][u];
}
return u;
}
int lca(int u, int v)
{
if(h[u]>h[v]) swap(u,v);
for(int i=LG-1;i>=0;i--)
{
if(st[i][v]!=-1&&h[st[i][v]]>=h[u])
{
v=st[i][v];
}
}
if(u==v) return u;
for(int i=LG-1;i>=0;i--)
{
if(st[i][v]!=-1&&st[i][v]!=st[i][u])
{
v=st[i][v]; u=st[i][u];
}
}
return st[0][u];
}
int type[77777];
int queries[77777];
struct node
{
int query[2];
int lazy[2];
node()
{
memset(query,-1,sizeof(query)); memset(lazy,-1,sizeof(lazy));
}
};
node T[77778*4];
void push(int id, int l, int r)
{
for(int z=0;z<2;z++)
{
if(T[id].lazy[z]!=-1)
{
T[id].query[z]=T[id].lazy[z];
if(r-l>=2)
{
T[id*2].lazy[z]=T[id*2+1].lazy[z]=T[id].lazy[z];
}
T[id].lazy[z]=-1;
}
}
}
void update(int id, int l, int r, int ql, int qr, int ty, int val)
{
push(id,l,r);
if(ql>=r||l>=qr) return ;
if(ql<=l&&r<=qr)
{
T[id].lazy[ty] = val;
push(id,l,r); return ;
}
int mid=(l+r)>>1;
update(id*2,l,mid,ql,qr,ty,val); update(id*2+1,mid,r,ql,qr,ty,val);
}
pair<int,int> query(int id, int l, int r, int pos)
{
push(id,l,r);
if(pos>=r||pos<l) return mp(-1,-1);
if(r-l<2) return mp(T[id].query[0],T[id].query[1]);
int mid=(l+r)>>1;
return max(query(id*2,l,mid,pos),query(id*2+1,mid,r,pos));
}
int n;
void update_up(int u, int v, int ty, int val)
{
//cerr<<"UPDATE "<<u<<' '<<v<<' '<<ty<<' '<<val<<'\n';
int cur = u;
while(h[nxt[cur]]>=h[v])
{
update(1,0,n,in[nxt[cur]],in[cur]+1,ty,val);
cur=st[0][nxt[cur]];
}
if(h[cur]>=h[v])
{
update(1,0,n,in[v],in[cur]+1,ty,val);
}
}
void update_path(int u, int v, int ty, int val)
{
int lc=lca(u,v);
//cerr<<"UPDATE PATH "<<u<<' '<<v<<' '<<lc<<'\n';
if(h[lc]<h[u])
{
int uup = go_up(u, h[u]-h[lc]-1);
update_up(u,uup,ty,val);
}
if(h[lc]<h[v])
{
int vup = go_up(v, h[v]-h[lc]-1);
update_up(v,vup,ty,val);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n; nxt[0]=0;
for(int i=0;i<n-1;i++)
{
int u,v; cin>>u>>v; u--; v--;
adj[u].pb(v); adj[v].pb(u);
}
dfs_siz(0,-1); dfs_hld(0,-1);
for(int i=1;i<LG;i++)
{
for(int j=0;j<n;j++)
{
if(st[i-1][j]==-1) st[i][j]=-1;
else st[i][j]=st[i-1][st[i-1][j]];
}
}
int q; cin>>q;
vector<pair<ii,ii> > querymax;
vector<pair<ii,ii> > querymin;
for(int i=0;i<q;i++)
{
char c; cin>>c;
int u,v; cin>>u>>v; u--; v--;
int val; cin>>val;
if(c=='M')
{
querymax.pb(mp(mp(val,i),mp(u,v)));
}
else
{
querymin.pb(mp(mp(val,i),mp(u,v)));
}
queries[i]=val; type[i] = (c=='M'?1:0);
}
sort(querymax.rbegin(),querymax.rend());
sort(querymin.begin(),querymin.end());
for(auto query:querymax)
{
int val = query.fi.fi; int lab = query.fi.se; int u = query.se.fi; int v = query.se.se;
update_path(u,v,1,lab);
}
for(auto query:querymin)
{
int val = query.fi.fi; int lab = query.fi.se; int u = query.se.fi; int v = query.se.se;
update_path(u,v,0,lab);
}
for(int i=1;i<n;i++)
{
ii labels = query(1,0,n,in[i]);
if(labels.fi!=-1) L[i] = queries[labels.fi];
if(labels.se!=-1) R[i] = queries[labels.se];
//cerr<<st[0][i]+1<<' '<<i+1<<' '<<L[i]<<' '<<R[i]<<'\n';
cout<<st[0][i]+1<<' '<<i+1<<' '<<R[i]<<'\n';
}
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:224:7: warning: unused variable 'val' [-Wunused-variable]
int val = query.fi.fi; int lab = query.fi.se; int u = query.se.fi; int v = query.se.se;
^~~
minmaxtree.cpp:229:7: warning: unused variable 'val' [-Wunused-variable]
int val = query.fi.fi; int lab = query.fi.se; int u = query.se.fi; int v = query.se.se;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
531 ms |
21728 KB |
Output is correct |
| 2 |
Correct |
502 ms |
21728 KB |
Output is correct |
| 3 |
Correct |
393 ms |
25120 KB |
Output is correct |
| 4 |
Correct |
459 ms |
29340 KB |
Output is correct |
| 5 |
Correct |
365 ms |
29348 KB |
Output is correct |
| 6 |
Correct |
519 ms |
31124 KB |
Output is correct |
| 7 |
Correct |
368 ms |
33172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
178 ms |
33172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
