#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;int Q;
int ar[100005];
int br[100005];
vector<int>e[70005];
vector<int>mxq[70005];
vector<int>mnq[70005];
vector<int>dmx[70005];
vector<int>dmn[70005];
int mxlm[70005];
int mnlm[70005];
char typ[70005];int ina[100005];int inb[100005];int inz[100005];
int jmp[20][100005];
int dph[100005];
void fdfs(int nw,int pa){
jmp[0][nw]=pa;
dph[nw]=dph[pa]+1;
for(int i=0;i<e[nw].size();i++){
int id=e[nw][i];
int v=ar[id]^br[id]^nw;
if(v==pa){continue;}
fdfs(v,nw);
}
}
int lca(int a,int b){
if(a==b){return a;}
if(dph[a]>dph[b]){swap(a,b);}
for(int i=19;i>=0;i--){
if(dph[jmp[i][b]]>=dph[a]){
b=jmp[i][b];
}
}
if(a==b){return a;}
for(int i=19;i>=0;i--){
if(jmp[i][a]!=jmp[i][b]){
a=jmp[i][a];b=jmp[i][b];
}
}
return jmp[0][a];
}
multiset<int>mxdp[70005];
multiset<int>mndp[70005];
void dfs(int nw,int pa,int paid){
if(e[nw].size()==1&&nw!=1){
for(int i=0;i<mxq[nw].size();i++){
mxdp[nw].insert(mxq[nw][i]);
}
if(mxdp[nw].size()){
mxlm[paid]=*(mxdp[nw].begin());
}
return;
}
int zo=nw^ar[e[nw][0]]^br[e[nw][0]];
for(int i=0;i<e[nw].size();i++){
int id=e[nw][i];
int v=ar[id]^br[id]^nw;
if(v==pa){continue;}
dfs(v,nw,id);
if(mxdp[v].size()>mxdp[zo].size()){
zo=v;
swap(e[nw][0],e[nw][i]);
}
}
swap(mxdp[nw],mxdp[zo]);
for(int i=1;i<e[nw].size();i++){
int id=e[nw][i];
int v=ar[id]^br[id]^nw;
if(v==pa){continue;}
for(auto it=mxdp[v].begin();it!=mxdp[v].end();it++){
mxdp[nw].insert((*it));
}
}
for(int i=0;i<mxq[nw].size();i++){
mxdp[nw].insert(mxq[nw][i]);
}
for(int i=0;i<dmx[nw].size();i++){
mxdp[nw].erase(mxdp[nw].find(dmx[nw][i]));
mxdp[nw].erase(mxdp[nw].find(dmx[nw][i]));
}
if(mxdp[nw].size()){
mxlm[paid]=*(mxdp[nw].begin());
}
}
void dfs2(int nw,int pa,int paid){
if(e[nw].size()==1&&nw!=1){
for(int i=0;i<mnq[nw].size();i++){
mndp[nw].insert(mnq[nw][i]);
}
if(mndp[nw].size()){
mnlm[paid]=*(mndp[nw].rbegin());
}
return;
}
int zo=nw^ar[e[nw][0]]^br[e[nw][0]];
for(int i=0;i<e[nw].size();i++){
int id=e[nw][i];
int v=ar[id]^br[id]^nw;
if(v==pa){continue;}
dfs2(v,nw,id);
if(mndp[v].size()>mndp[zo].size()){
zo=v;
swap(e[nw][0],e[nw][i]);
}
}
swap(mndp[nw],mndp[zo]);
for(int i=1;i<e[nw].size();i++){
int id=e[nw][i];
int v=ar[id]^br[id]^nw;
if(v==pa){continue;}
for(auto it=mndp[v].begin();it!=mndp[v].end();it++){
mndp[nw].insert((*it));
}
}
for(int i=0;i<mnq[nw].size();i++){
mndp[nw].insert(mnq[nw][i]);
}
for(int i=0;i<dmn[nw].size();i++){
mndp[nw].erase(mndp[nw].find(dmn[nw][i]));
mndp[nw].erase(mndp[nw].find(dmn[nw][i]));
}
if(mndp[nw].size()){
mnlm[paid]=*(mndp[nw].rbegin());
}
}
void build(){
fdfs(1,0);
for(int i=1;i<=19;i++){
for(int j=1;j<=n;j++){
jmp[i][j]=jmp[i-1][jmp[i-1][j]];
}
}
for(int i=1;i<=Q;i++){
if(typ[i]=='M'){
mxq[ina[i]].push_back(inz[i]);
mxq[inb[i]].push_back(inz[i]);
dmx[lca(ina[i],inb[i])].push_back(inz[i]);
}else{
mnq[ina[i]].push_back(inz[i]);
mnq[inb[i]].push_back(inz[i]);
dmn[lca(ina[i],inb[i])].push_back(inz[i]);
}
}
for(int i=1;i<=n-1;i++){
mxlm[i]=1e12;
mnlm[i]=-mxlm[i];
}
dfs(1,0,0);
dfs2(1,0,0);
}
map<int,int>mp;int rmp[200005];
void lisanhua(){
vector<int>vc;
for(int i=1;i<=Q;i++){
vc.push_back(inz[i]);
}
sort(vc.begin(),vc.end());
for(int i=0;i<Q;i++){
mp[vc[i]]=i+1;
rmp[i+1]=vc[i];
}
}
int vis[200005];
int hs[200005];
int ans[200005];
int dgr[200005];
int vvis[200005];
vector<pair<int,int>>ne[200005];
signed main(){
cin>>n;
for(int i=1;i<=n-1;i++){
cin>>ar[i]>>br[i];
e[ar[i]].push_back(i);
e[br[i]].push_back(i);
}
cin>>Q;
for(int i=1;i<=Q;i++){
cin>>typ[i]>>ina[i]>>inb[i]>>inz[i];
//assert(inz[i]<-1e9);
}
build();/*
for(int i=1;i<=n-1;i++){
cout<<mnlm[i]<<" "<<mxlm[i]<<endl;
}*/
lisanhua();
for(int i=1;i<=n-1;i++){
int cnt=0;
if(mnlm[i]<=1e9&&mnlm[i]>=-1e9){
//mnlm[i]=mp[mnlm[i]];
cnt++;
}
if(mxlm[i]<=1e9&&mxlm[i]>=-1e9){
// mxlm[i]=mp[mxlm[i]];
cnt++;
}
if(cnt==0){
ans[i]=1e9;
continue;
}
if(cnt==1){
if(abs(mxlm[i])<=1e9){
vis[i]=1;
hs[mp[mxlm[i]]]=1;
ans[i]=mxlm[i];
}else{
vis[i]=1;
hs[mp[mnlm[i]]]=1;
ans[i]=mnlm[i];
}
continue;
}
ne[mp[mxlm[i]]].push_back({mp[mnlm[i]],i});
ne[mp[mnlm[i]]].push_back({mp[mxlm[i]],i});
dgr[mp[mxlm[i]]]++;
dgr[mp[mnlm[i]]]++;
}/*
for(int i=1;i<=n-1;i++){
cout<<mnlm[i]<<" "<<mxlm[i]<<endl;
}*/
queue<int>q;
for(int i=1;i<=Q;i++){
if(dgr[i]==1){
q.push(i);
}
}
while(q.size()){
int nw=q.front();
q.pop();
vvis[nw]=1;
for(int i=0;i<ne[nw].size();i++){
int eid=ne[nw][i].second;
if(vis[eid]){continue;}
int v=ne[nw][i].first;
vis[eid]=1;
dgr[v]--;
if(dgr[v]==1){
q.push(v);
}
if(hs[nw]==0){
ans[eid]=rmp[nw];
hs[nw]=1;
}else{
ans[eid]=rmp[v];
hs[v]=1;
}
}
}
for(int nw=1;nw<=Q;nw++){
if(vvis[nw]){continue;}
for(int i=0;i<ne[nw].size();i++){
int eid=ne[nw][i].second;
if(vis[eid]){continue;}
int v=ne[nw][i].first;
vis[eid]=1;
if(hs[nw]==0){
ans[eid]=rmp[nw];
hs[nw]=1;
}else{
ans[eid]=rmp[v];
hs[v]=1;
}
}
}
for(int i=1;i<=n-1;i++){
cout<<ar[i]<<" "<<br[i]<<" "<<ans[i]<<endl;
}
}
Compilation message
minmaxtree.cpp: In function 'void fdfs(long long int, long long int)':
minmaxtree.cpp:20:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs(long long int, long long int, long long int)':
minmaxtree.cpp:48:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0;i<mxq[nw].size();i++){
| ~^~~~~~~~~~~~~~~
minmaxtree.cpp:58:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
minmaxtree.cpp:69:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i=1;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
minmaxtree.cpp:77:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0;i<mxq[nw].size();i++){
| ~^~~~~~~~~~~~~~~
minmaxtree.cpp:80:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i=0;i<dmx[nw].size();i++){
| ~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs2(long long int, long long int, long long int)':
minmaxtree.cpp:91:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i=0;i<mnq[nw].size();i++){
| ~^~~~~~~~~~~~~~~
minmaxtree.cpp:101:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
minmaxtree.cpp:112:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i=1;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
minmaxtree.cpp:120:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i=0;i<mnq[nw].size();i++){
| ~^~~~~~~~~~~~~~~
minmaxtree.cpp:123:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i=0;i<dmn[nw].size();i++){
| ~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:239:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
239 | for(int i=0;i<ne[nw].size();i++){
| ~^~~~~~~~~~~~~~
minmaxtree.cpp:261:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
261 | for(int i=0;i<ne[nw].size();i++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
49752 KB |
Output is correct |
| 2 |
Correct |
7 ms |
49756 KB |
Output is correct |
| 3 |
Correct |
7 ms |
49756 KB |
Output is correct |
| 4 |
Correct |
8 ms |
49756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
396 ms |
68124 KB |
Output is correct |
| 2 |
Correct |
317 ms |
70860 KB |
Output is correct |
| 3 |
Correct |
290 ms |
66072 KB |
Output is correct |
| 4 |
Correct |
317 ms |
68260 KB |
Output is correct |
| 5 |
Correct |
314 ms |
67552 KB |
Output is correct |
| 6 |
Correct |
335 ms |
65144 KB |
Output is correct |
| 7 |
Correct |
359 ms |
63628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
59588 KB |
Output is correct |
| 2 |
Correct |
212 ms |
59656 KB |
Output is correct |
| 3 |
Correct |
208 ms |
61384 KB |
Output is correct |
| 4 |
Correct |
230 ms |
63516 KB |
Output is correct |
| 5 |
Correct |
231 ms |
60024 KB |
Output is correct |
| 6 |
Correct |
261 ms |
60612 KB |
Output is correct |
| 7 |
Correct |
228 ms |
59376 KB |
Output is correct |
| 8 |
Incorrect |
227 ms |
59216 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
49752 KB |
Output is correct |
| 2 |
Correct |
7 ms |
49756 KB |
Output is correct |
| 3 |
Correct |
7 ms |
49756 KB |
Output is correct |
| 4 |
Correct |
8 ms |
49756 KB |
Output is correct |
| 5 |
Correct |
396 ms |
68124 KB |
Output is correct |
| 6 |
Correct |
317 ms |
70860 KB |
Output is correct |
| 7 |
Correct |
290 ms |
66072 KB |
Output is correct |
| 8 |
Correct |
317 ms |
68260 KB |
Output is correct |
| 9 |
Correct |
314 ms |
67552 KB |
Output is correct |
| 10 |
Correct |
335 ms |
65144 KB |
Output is correct |
| 11 |
Correct |
359 ms |
63628 KB |
Output is correct |
| 12 |
Correct |
211 ms |
59588 KB |
Output is correct |
| 13 |
Correct |
212 ms |
59656 KB |
Output is correct |
| 14 |
Correct |
208 ms |
61384 KB |
Output is correct |
| 15 |
Correct |
230 ms |
63516 KB |
Output is correct |
| 16 |
Correct |
231 ms |
60024 KB |
Output is correct |
| 17 |
Correct |
261 ms |
60612 KB |
Output is correct |
| 18 |
Correct |
228 ms |
59376 KB |
Output is correct |
| 19 |
Incorrect |
227 ms |
59216 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
