#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);
}
}
ii labels[77777];
int par2[77777];
set<ii> G[77777];
bool visited[77777];
int h2[77777];
ii backedge;
int backedgelab;
int paredge[77777];
void dfs2(int u, int p)
{
visited[u]=1;
for(ii X:G[u])
{
int v=X.fi; int lab=X.se;
if(v==p) continue;
if(visited[v])
{
if(h2[v]<h2[u])
{
backedge=mp(u,v); //v is parent
backedgelab=lab;
}
}
else
{
paredge[v]=lab;
par2[v]=u; h2[v]=h2[u]+1; ans[lab] = queries[v];
dfs2(v,u);
}
}
}
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);
}
memset(ans,-1,sizeof(ans));
for(int i=1;i<n;i++)
{
labels[i] = query(1,0,n,in[i]);
if(labels[i].fi!=-1) L[i] = queries[labels[i].fi];
if(labels[i].se!=-1) R[i] = queries[labels[i].se];
//cerr<<st[0][i]+1<<' '<<i+1<<' '<<L[i]<<' '<<R[i]<<'\n';
//cout<<st[0][i]+1<<' '<<i+1<<' '<<R[i]<<'\n';
}
for(int i=1;i<n;i++)
{
if(labels[i].fi==-1&&labels[i].se==-1) continue;
//cerr<<i<<' '<<labels[i].fi<<' '<<labels[i].se<<'\n';
if(labels[i].se==-1)
{
ans[i]=L[i]; visited[labels[i].fi]=1;
}
else if(labels[i].fi==-1)
{
ans[i]=R[i]; visited[labels[i].se]=1;
}
else
{
auto it = G[labels[i].fi].lower_bound(mp(labels[i].se,-100));
if(it->fi==labels[i].se)
{
visited[labels[i].se]=1;
visited[labels[i].fi]=1;
ans[it->se] = L[i];
ans[i] = R[i];
}
else
{
G[labels[i].fi].insert(mp(labels[i].se, i)); G[labels[i].se].insert(mp(labels[i].fi, i));
}
}
}
queue<int> Q;
for(int i=0;i<q;i++)
{
if(visited[i]) Q.push(i);
}
while(!Q.empty())
{
int u = Q.front(); Q.pop();
while(!G[u].empty())
{
ii V=(*G[u].begin());
int v=V.fi; int lab=V.se;
if(ans[lab]==-1)
{
ans[lab] = queries[v];
}
G[v].erase(mp(u,lab));
if(!visited[v])
{
Q.push(v); visited[v]=1;
}
G[u].erase(G[u].begin());
}
}
for(int i=0;i<q;i++)
{
if(!visited[i])
{
backedge=mp(-1,-1);
dfs2(i,-1);
int u = backedge.fi; int v = backedge.se;
assert(u>=0);
//u go up to v
//paredge from u to root is flipped
int cur = u;
while(cur!=i)
{
ans[paredge[cur]] = queries[par2[cur]];
cur=par2[cur];
}
ans[backedgelab] = queries[u];
}
}
for(int i=1;i<n;i++)
{
if(ans[i]==-1) ans[i] = L[i];
}
for(int i=1;i<n;i++)
{
cout<<st[0][i]+1<<' '<<i+1<<' '<<ans[i]<<'\n';
}
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:257: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:262: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:332:29: warning: unused variable 'v' [-Wunused-variable]
int u = backedge.fi; int v = backedge.se;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11128 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
11236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
401 ms |
26528 KB |
Output is correct |
| 2 |
Correct |
446 ms |
26528 KB |
Output is correct |
| 3 |
Correct |
317 ms |
26528 KB |
Output is correct |
| 4 |
Correct |
321 ms |
27292 KB |
Output is correct |
| 5 |
Correct |
343 ms |
27292 KB |
Output is correct |
| 6 |
Correct |
402 ms |
27292 KB |
Output is correct |
| 7 |
Correct |
339 ms |
27292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
223 ms |
27292 KB |
Output is correct |
| 2 |
Correct |
283 ms |
27292 KB |
Output is correct |
| 3 |
Correct |
230 ms |
28160 KB |
Output is correct |
| 4 |
Correct |
253 ms |
30408 KB |
Output is correct |
| 5 |
Correct |
215 ms |
30408 KB |
Output is correct |
| 6 |
Correct |
254 ms |
30744 KB |
Output is correct |
| 7 |
Correct |
215 ms |
31352 KB |
Output is correct |
| 8 |
Correct |
210 ms |
32648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11128 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
11236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
