#include <bits/stdc++.h>
#define pb push_back
#define mpf make_pair
#define MAXN 100100
#define MAXD 20
#define MAXINT 1000000000
#define MININT -1
#define l (2*cur)
#define r ((2*cur)+1)
#define mid (a+b)/2
using namespace std;
int N;
vector<int> adj[MAXN] , edgeidx[MAXN];
int treesz[MAXN] , depth[MAXN] , lca[MAXN][MAXD] , edgebelow[MAXN] , edgeabove[MAXN] , edgetoseg[MAXN] , segtoedge[MAXN];
int tree[4*MAXN][2] , lazy[4*MAXN][2] , fn[MAXN][2] , ee[MAXN][2] , topchain[MAXN];
map <int,bool> mp;
void segupd(int cur , int a , int b , int i , int j , int val , int t){
if(a > j || b < i) return;
//cout << cur << " " << a << " " << b << " " << i << " " << j << " " << val << " " << t << endl;
if(lazy[cur][t] != 0){
if(a == b){
int u = lazy[cur][t];
if(t == 0) tree[cur][t] = max(tree[cur][t] , u);
else tree[cur][t] = min(tree[cur][t] , u);
goto exit;
}
int u = lazy[cur][t];
if(lazy[l][t] == 0) lazy[l][t] = u;
else if(t == 0) lazy[l][t] = max(lazy[l][t] , u);
else lazy[l][t] = min(lazy[l][t] , u);
if(lazy[r][t] == 0) lazy[r][t] = u;
else if(t == 0) lazy[r][t] = max(lazy[r][t] , u);
else lazy[r][t] = min(lazy[r][t] , u);
lazy[cur][t] = 0;
}
exit:
if(a >= i && b <= j){
tree[cur][t] = (t == 0) ? max(tree[cur][t] , val) : min(tree[cur][t] , val);
lazy[cur][t] = val;
return;
}
segupd(l , a , mid , i , j , val , t);
segupd(r , mid + 1 , b , i , j , val , t);
tree[cur][t] = (t == 0) ? max(tree[l][t] , tree[r][t]) : min(tree[l][t] , tree[r][t]);
}
void segupd(int i , int j , int val , int t){
segupd(1 , 0 , N-2 , i , j , val , t);
}
void segpush(int cur , int a , int b , int t){
if(lazy[cur][t] != 0){
if(a == b){
if(t == 0) tree[cur][t] = max(tree[cur][t] , lazy[cur][t]);
else tree[cur][t] = min(tree[cur][t] , lazy[cur][t]);
fn[segtoedge[a]][t] = tree[cur][t];
return;
}
int u = lazy[cur][t];
if(lazy[l][t] == 0) lazy[l][t] = u;
else if(t == 0) lazy[l][t] = max(lazy[l][t] , u);
else lazy[l][t] = min(lazy[l][t] , u);
if(lazy[r][t] == 0) lazy[r][t] = u;
else if(t == 0) lazy[r][t] = max(lazy[r][t] , u);
else lazy[r][t] = min(lazy[r][t] , u);
lazy[cur][t] = 0;
}
if(a == b){
fn[segtoedge[a]][t] = tree[cur][t];
return;
}
segpush(l , a , mid , t);
segpush(r , mid + 1 , b , t);
}
void dfsForSize(int cur , int pr){
treesz[cur]++;
for(int i=0; i<adj[cur].size(); i++){
int nxt = adj[cur][i];
if(nxt == pr) continue;
lca[nxt][0] = cur;
depth[nxt] = depth[cur] + 1;
edgeabove[nxt] = edgeidx[cur][i];
dfsForSize(nxt , cur);
treesz[cur] += treesz[nxt];
}
}
void initLCA(){
for(int d = 1; d<MAXD; d++)
for(int i=0; i<N; i++)
lca[i][d] = lca[ lca[i][d-1] ][d-1];
}
void dfsForHLD(int cur , int topCh , int pr , int &segtreeidx , int idx){
if(pr != -1){
edgetoseg[ edgeidx[pr][idx] ] = segtreeidx;
segtoedge[ segtreeidx++ ] = edgeidx[pr][idx];
}
topchain[cur] = topCh;
int k = -1;
for(int i=0; i<adj[cur].size(); i++){
int nxt = adj[cur][i];
if(nxt == pr) continue;
if(k == -1 || treesz[ adj[cur][k] ] < treesz[ adj[cur][i] ]) k = i;
}
if(k == -1) return;
edgebelow[cur] = edgeidx[cur][k];
dfsForHLD(adj[cur][k] , topCh , cur , segtreeidx , k);
for(int i=0; i<adj[cur].size(); i++){
int nxt = adj[cur][i];
if(nxt == pr || i == k) continue;
dfsForHLD(nxt , nxt , cur , segtreeidx , i);
}
}
void initHLD(){
dfsForSize(0 , -1);
initLCA();
int segtreeidx = 0;
dfsForHLD(0 , 0 , -1 , segtreeidx , -1);
}
int getLCA(int u , int v){
if(depth[u] < depth[v]) swap(u,v);
for(int d = MAXD-1; d>=0; d--)
if(depth[u] - (1 << d) >= depth[v]) u = lca[u][d];
for(int d=MAXD-1; d>=0; d--)
if(lca[u][d] != lca[v][d]){ u = lca[u][d] , v = lca[v][d];}
if(u != v){
u = lca[u][0];
v = lca[v][0];
}
return u;
}
void hld(int ch , int pr , int val , int t){
while(ch != pr){
if(topchain[ch] == ch){
segupd(edgetoseg[ edgeabove[ch] ] , edgetoseg[ edgeabove[ch] ] , val , t);
ch = lca[ch][0];
}
else if(depth[ topchain[ch] ] > depth[pr] ){
segupd(edgetoseg[ edgebelow[topchain[ch]] ] , edgetoseg[ edgeabove[ch] ] , val , t);
ch = topchain[ch];
}
else{
//cout << ch << " " << edgeabove[ch] << " + " << pr << " " << edgebelow[pr] << endl;
//cout << edgetoseg[ edgeabove[ch] ] << " - " << edgetoseg[ edgebelow[pr] ] << endl;
segupd(edgetoseg[ edgebelow[pr] ] , edgetoseg[ edgeabove[ch] ] , val , t);
break;
}
}
}
void output(){
for(int i=0; i<N-1; i++){
cout << edgetoseg[i] << " " << edgeabove[i] << " " << edgebelow[i] << " " << endl;
}
cout << endl;
for(int i=0; i<N; i++){
cout << treesz[i] << " " << depth[i] << " " << lca[i][0] << " " << topchain[i] << endl;
}
cout << endl;
cout << endl;
}
int main(){
std::cin >> N;
for(int i=0; i<4*MAXN; i++) tree[i][1] = MAXINT , tree[i][0] = MININT;
int rr = 0;
for(int i=0; i<N-1; i++){
int u,v; cin >> u >> v; u--;v--;
ee[rr][0] = u + 1 , ee[rr++][1] = v + 1;
adj[u].pb(v);
adj[v].pb(u);
edgeidx[u].pb(i);
edgeidx[v].pb(i);
}
initHLD();
//output();
int Q; cin >> Q;
while(Q--){
char c; cin >> c;
int u,v,w;cin >> u >> v >> w;u--;v--;
//rr++;
//ee[rr][0] = u , ee[rr++][1] = v;
int pr = getLCA(u , v);
//cout << "LCA " << pr << endl;
int t;
if(c == 'm') t = 0;
else t = 1;
hld(u , pr , w , t) , hld(v , pr,w,t);
}
segpush(1 , 0 , N-2 , 0);
segpush(1 , 0 , N-2 , 1);
/*for(int i=0; i<N; i++)
cout << i << " " << fn[i][0] << " " << fn[i][1] << endl;
cout << endl; cout << endl;*/
//output();
for(int i=0; i<N-1; i++)
cout << ee[i][0] << " " << ee[i][1] << " " << fn[i][1] << '\n';
/*for(int i=0; i<N-1; i++){
map<int,int>::iterator it;
it = mp.find(fn[i][0]);
if(it == mp.end()) mp[fn[i][0]] = 1;
else mp[fn[i][0]]++;
it = mp.find(fn[i][1]);
if(it == mp.end()) mp[fn[i][1]] = 1;
else mp[fn[i][1]]++;
}
for(int i=0; i<N-1; i++){
cout << ee[i][0] << " " << ee[i][1] << " ";
int u = fn[i][0] , v = fn[i][1];
if(u == MININT && v == MAXINT) cout << "69" << endl;
else if(u == MININT) {cout << v << endl; mp[v] = 0;}
else if(v == MAXINT) {cout << u << endl; mp[u] = 0;}
else if(mp[u] == 0) {cout << v << endl; mp[v] = 0;}
else if(mp[v] == 0) {cout << u << endl; mp[u] = 0;}
else if(mp[u] == 1) {cout << u << endl; mp[u] = 0;mp[v]--;}
*/
return 0;
}
Compilation message
minmaxtree.cpp: In function 'void dfsForSize(int, int)':
minmaxtree.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[cur].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfsForHLD(int, int, int, int&, int)':
minmaxtree.cpp:121:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[cur].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:131:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[cur].size(); i++){
~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
8192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
444 ms |
30076 KB |
Output is correct |
| 2 |
Correct |
432 ms |
26892 KB |
Output is correct |
| 3 |
Correct |
466 ms |
28920 KB |
Output is correct |
| 4 |
Correct |
549 ms |
31116 KB |
Output is correct |
| 5 |
Correct |
584 ms |
28264 KB |
Output is correct |
| 6 |
Correct |
458 ms |
27576 KB |
Output is correct |
| 7 |
Correct |
386 ms |
26616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
25876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
8192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
