#include <bits/stdc++.h>
#define maxN 70007
using namespace std;
struct cvor{
int c,d,s,val,par,p;
};
struct segment{
int l,v;
};
cvor a[maxN];
vector <int> adj[maxN],v[maxN];
vector <segment> seg[maxN];
int n,m,i,j,x,y,c=0,t[maxN];
void dfs(int n){
a[n].s=1;
for(int i=0;i<adj[n].size();i++){
if(adj[n][i]==a[n].par) continue;
a[adj[n][i]].par=n;
a[adj[n][i]].d=a[n].d+1;
dfs(adj[n][i]);
a[n].s+=a[adj[n][i]].s;
}
}
void dodela(int n){
a[n].c=c;
a[n].p=v[c].size();
v[c].push_back(n);
if(n!=0 && adj[n].size()==1) {c++; return;}
int tmp,m=0;
for(int i=0;i<adj[n].size();i++){
if(adj[n][i]==a[n].par) continue;
if(a[adj[n][i]].s>m) {m=a[adj[n][i]].s; tmp=adj[n][i];}
}
//cout<<n<<" "<<tmp<<endl;
dodela(tmp);
for(int i=0;i<adj[n].size();i++){
if(adj[n][i]==a[n].par || adj[n][i]==tmp) continue;
t[c]=adj[n][i];
dodela(adj[n][i]);
}
}
vector <int> _merge(vector <int> a,vector <int> b){
vector <int> ans;
int i,j;
i=0; j=0;
while(i<a.size() && j<b.size()){
if(a[i]<b[j]) {ans.push_back(a[i]); i++;}
else {ans.push_back(b[j]); j++;}
}
while(i<a.size()){ans.push_back(a[i]); i++;}
while(j<b.size()){ans.push_back(b[j]); j++;}
return ans;
}
void propagate(int x,int n,int l,int d){
if(seg[x][n].l==0) return;
if(l==d){
seg[x][n].v=seg[x][n].l;
seg[x][n].l=0;
return;
}
seg[x][2*n].l=seg[x][2*n+1].l=seg[x][n].l;
seg[x][n].l=0;
}
void update(int x,int n,int l,int d,int a,int b,int v){
propagate(x,n,l,d);
if(l>=a && d<=b){seg[x][n].l=v; return;}
int m=(l+d)/2;
if(a<=m) update(x,2*n,l,m,a,b,v);
if(b>=m+1) update(x,2*n+1,m+1,d,a,b,v);
seg[x][n].v=max(seg[x][2*n].v,seg[x][2*n+1].v);
}
int query(int x,int n,int l,int d,int y){
propagate(x,n,l,d);
if(l==d) return seg[x][n].v;
int m=(l+d)/2;
if(y<=m) return query(x,2*n,l,m,y);
return query(x,2*n+1,m+1,d,y);
}
vector <int> e;
int p[maxN];
pair<int,int> spar[2*maxN][22];
void ojler(int n){
e.push_back(n);
for(int i=0;i<adj[n].size();i++){
if(adj[n][i]==a[n].par) continue;
ojler(adj[n][i]);
e.push_back(n);
}
}
void upd(int x,int y,int val){
if(a[x].d<=a[y].d) return;
int tmp=t[a[x].c];
if(a[tmp].d>a[y].d){
update(a[x].c,1,0,v[a[x].c].size()-1,0,a[x].p,val);
upd(a[tmp].par,y,val);
return;
}
update(a[x].c,1,0,v[a[x].c].size()-1,a[y].p,a[x].p,val);
}
struct uslov{
int a,b,v;
};
vector <uslov> u;
uslov pom;
bool poredi(uslov a,uslov b){
return a.v>b.v;
}
int lca(int x,int y){
pair<int,int> tmp={maxN,maxN};
for(int j = 21; j >= 0; j--) {
if(x + (1 << j) - 1 <= y) {
tmp = min(tmp, spar[x][j]);
x += 1 << j;
}
}
return tmp.second;
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin>>n;
for(i=1;i<n;i++){
cin>>x>>y;
x--;
y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
a[0].par=-1;
dfs(0);
dodela(0);
t[0]=0;
for(i=0;i<c;i++){
segment tmp;
tmp.l=0;
tmp.v=0;
for(j=0;j<4*v[i].size();j++) seg[i].push_back(tmp);
}
ojler(0);
for(i=e.size()-1;i>=0;i--){
p[e[i]]=i;
spar[i][0]={a[e[i]].d,e[i]};
}
for(j=1;j<22;j++){
for(i=0;i<e.size();i++){
if(i+1<<j>e.size()) break;
spar[i][j]=min(spar[i+(1<<(j-1))][j-1],spar[i][j-1]);
}
}
cin>>m;
for(i=0;i<m;i++){
char o;
cin>>o;
cin>>x>>y;
x--;
y--;
pom.a=x;
pom.b=y;
cin>>x;
pom.v=x;
u.push_back(pom);
}
sort(u.begin(),u.end(),poredi);
for(i=0;i<m;i++){
int l=lca(p[u[i].a],p[u[i].b]);
upd(u[i].a,l,u[i].v);
upd(u[i].b,l,u[i].v);
}
for(i=1;i<n;i++) cout<<i+1<<" "<<a[i].par+1<<" "<<query(a[i].c,1,0,v[a[i].c].size()-1,a[i].p)<<endl;
return 0;
}
Compilation message
minmaxtree.cpp: In function 'void dfs(int)':
minmaxtree.cpp:20:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[n].size();i++){
~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dodela(int)':
minmaxtree.cpp:35:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[n].size();i++){
~^~~~~~~~~~~~~~
minmaxtree.cpp:41:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[n].size();i++){
~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'std::vector<int> _merge(std::vector<int>, std::vector<int>)':
minmaxtree.cpp:52:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<a.size() && j<b.size()){
~^~~~~~~~~
minmaxtree.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<a.size() && j<b.size()){
~^~~~~~~~~
minmaxtree.cpp:56:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<a.size()){ans.push_back(a[i]); i++;}
~^~~~~~~~~
minmaxtree.cpp:57:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j<b.size()){ans.push_back(b[j]); j++;}
~^~~~~~~~~
minmaxtree.cpp: In function 'void ojler(int)':
minmaxtree.cpp:95:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[n].size();i++){
~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:154:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<4*v[i].size();j++) seg[i].push_back(tmp);
~^~~~~~~~~~~~~~
minmaxtree.cpp:162:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<e.size();i++){
~^~~~~~~~~
minmaxtree.cpp:163:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
if(i+1<<j>e.size()) break;
~^~
minmaxtree.cpp:163:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i+1<<j>e.size()) break;
~~~~~~^~~~~~~~~
minmaxtree.cpp: In function 'void dodela(int)':
minmaxtree.cpp:42:24: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(adj[n][i]==a[n].par || adj[n][i]==tmp) continue;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
302 ms |
45416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
223 ms |
41592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
