//P4116 #include <bits/stdc++.h> #define int long long using namespace std; const int md=201314; int n,m,tot,w[1000010],c[1000010],son[1000010],hed[1000010],siz[1000010]; int top[1000010],col[1000010],ver[1000010],nxt[1000010],idx[1000010]; int fa[1000010],dep[1000010],id[1000010],sm,cnt=1,ans[1000010]; set<int> s[100010]; void add(int u,int v){ver[++tot]=v,nxt[tot]=hed[u],hed[u]=tot; } void dfs1(int u,int faa){dep[u]=dep[faa]+1;fa[u]=faa;siz[u]=1;for(int i=hed[u];i;i=nxt[i]){int v=ver[i];if(v==faa){continue;}dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[son[u]]){son[u]=v;}} } void dfs2(int u,int tp){top[u]=tp;id[u]=++sm;idx[sm]=u;if(son[u]){dfs2(son[u],tp);}for(int i=hed[u];i;i=nxt[i]){int v=ver[i];if(v==fa[u]||v==son[u]){continue;}dfs2(v,v);} } void Change(int x){col[x]^=1;if(col[x]==1){s[top[x]].insert(id[x]);}else{s[top[x]].erase(id[x]);} } int Ask(int x){int ans=1e9;while(x){int k=(*s[top[x]].begin());if(s[top[x]].size()){if(dep[idx[k]]<=dep[x]){ans=idx[k];// cout<<" - "<<k<<" "<<ans<<endl; }}x=fa[top[x]];}if(ans==1e9){return -1;}return ans; } signed main(){ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<n;i++){int u,v;cin>>u>>v;add(u,v);add(v,u);}dfs1(1,0);dfs2(1,1); for(int i=1;i<=m;i++){int opt,x;cin>>opt>>x;if(opt==0){Change(x);}if(opt==1){cout<<Ask(x)<<endl;}}return 0; } /* 5 5 1 2 1 3 2 4 2 5 0 1 1 5 0 5 1 5 0 5 1 5 */
//P3313 #include <bits/stdc++.h> #define int long long using namespace std; int n,q,w[1000010],c[1000010],son[1000010],hed[1000010],siz[1000010]; int top[1000010],root[1000010],ver[1000010],nxt[1000010]; int fa[1000010],dep[1000010],id[1000010],sm,cnt,tot; struct SegmentTree{int lc,rc,sum,fl,mx; }a[100010<<4]; void add(int u,int v){ver[++tot]=v,nxt[tot]=hed[u],hed[u]=tot; } void dfs1(int u,int faa){dep[u]=dep[faa]+1;fa[u]=faa;siz[u]=1;for(int i=hed[u];i;i=nxt[i]){int v=ver[i];if(v==faa){continue;}dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[son[u]]){son[u]=v;}} } void dfs2(int u,int tp){top[u]=tp;id[u]=++sm;if(son[u]){dfs2(son[u],tp);}for(int i=hed[u];i;i=nxt[i]){int v=ver[i];if(v==fa[u]||v==son[u]){continue;}dfs2(v,v);} } void Update(int x){a[x].sum=a[a[x].lc].sum+a[a[x].rc].sum;a[x].mx=max(a[a[x].lc].mx,a[a[x].rc].mx); } void Add(int p,int l,int r,int &x,int k){if(!x){x=++cnt;}a[x].mx=max(a[x].mx,k);a[x].sum+=k;if(l==r){return;}int mid=(l+r)/2;if(p<=mid){Add(p,l,mid,a[x].lc,k);}if(p>mid){Add(p,mid+1,r,a[x].rc,k);}return ; } void Cover0(int p,int l,int r,int &x){if(l==r){a[x].sum=a[x].mx=0;return;}int mid=(l+r)/2;if(p<=mid){Cover0(p,l,mid,a[x].lc);}if(p>mid){Cover0(p,mid+1,r,a[x].rc);}Update(x);return ; } int AskSum(int u,int v,int l,int r,int x){if(l>=u&&r<=v){return a[x].sum;}int mid=(l+r)/2,res=0;if(u<=mid){res+=AskSum(u,v,l,mid,a[x].lc);}if(v>mid){res+=AskSum(u,v,mid+1,r,a[x].rc);}return res; } int AskRdSum(int x,int y,int k){int ans=0;while(top[x]!=top[y]){if(dep[top[x]]>dep[top[y]]){ans+=AskSum(id[top[x]],id[x],1,n,root[k]);x=fa[top[x]];continue;}ans+=AskSum(id[top[y]],id[y],1,n,root[k]);y=fa[top[y]];}if(dep[x]>dep[y]){swap(x,y);}ans+=AskSum(id[x],id[y],1,n,root[k]);return ans; } int AskMax(int u,int v,int l,int r,int x){if(l>=u&&r<=v){return a[x].mx;}int mid=(l+r)/2,ans=0;if(u<=mid){ans=max(ans,AskMax(u,v,l,mid,a[x].lc));}if(v>mid){ans=max(ans,AskMax(u,v,mid+1,r,a[x].rc));}return ans; } int AskRdMax(int x,int y,int k){int ans=0;while(top[x]!=top[y]){if(dep[top[x]]>dep[top[y]]){ans=max(ans,AskMax(id[top[x]],id[x],1,n,root[k]));x=fa[top[x]];continue;}ans=max(ans,AskMax(id[top[y]],id[y],1,n,root[k]));y=fa[top[y]];}if(dep[x]>dep[y]){swap(x,y);}ans=max(ans,AskMax(id[x],id[y],1,n,root[k]));return ans; } signed main(){ios::sync_with_stdio(0);cin>>n>>q;for(int i=1;i<=n;i++){cin>>w[i]>>c[i];}for(int i=1,u,v;i<n;i++){cin>>u>>v;add(u,v);add(v,u);}dfs1(1,0);dfs2(1,1);for(int i=1;i<=n;i++){Add(id[i],1,n,root[c[i]],w[i]);}for(int i=1,x,y;i<=q;i++){char opt[4];cin>>opt>>x>>y;if(opt[1]=='C'){Cover0(id[x],1,n,root[c[x]]);Add(id[x],1,n,root[y],w[x]);c[x]=y;}if(opt[1]=='W'){Cover0(id[x],1,n,root[c[x]]);Add(id[x],1,n,root[c[x]],y);w[x]=y;}if(opt[1]=='S'){cout<<AskRdSum(x,y,c[x])<<endl;}if(opt[1]=='M'){cout<<AskRdMax(x,y,c[x])<<endl;}}return 0; }
//P4114 #include <bits/stdc++.h> #define int long long using namespace std; int n,m,tot,cnt,ver[1000010],hed[1000010],nxt[1000010],dfn[1000010],low[1000010]; int idx[1000010],siz[1000010],w[1000010],fa[1000010],dep[1000010],top[1000010]; int son[1000010],sm; struct SegmentTree{int l,r,mx,cov; }a[4000040]; void add(int a,int b){ver[++tot]=b,nxt[tot]=hed[a],hed[a]=tot; } /*void Spread(int p){if(a[p].cov){a[p*2].cov=a[p].cov;a[p*2+1].cov=a[p].cov;a[p*2].mx=max(a[p*2].mx,a[p].cov);a[p*2+1].mx=max(a[p*2+1].mx,a[p].cov);a[p].cov=0;}return ; }*/ void Build(int p,int l,int r){a[p].l=l,a[p].r=r;if(l==r){//cout<<p<<" "<<l<<" - "<<w[idx[l]]<<endl;a[p].mx=w[idx[l]];return ;}int mid=(l+r)/2;Build(p*2,l,mid);Build(p*2+1,mid+1,r);a[p].mx=max(a[p*2].mx,a[p*2+1].mx);return ; } void Change(int p,int l,int r,int x){//cout<<p<<endl;if(a[p].l>=l&&a[p].r<=r){a[p].mx=x;a[p].cov=x;return ;}//Spread(p);int mid=(a[p].l+a[p].r)/2;if(l<=mid){Change(p*2,l,r,x);}if(r>mid){Change(p*2+1,l,r,x);}a[p].mx=max(a[p*2].mx,a[p*2+1].mx);return ; } int Ask(int p,int l,int r){//cout<<p<<a[p].l<<a[p].r<<a[p].mx<<endl;if(a[p].l>=l&&a[p].r<=r){return a[p].mx;}//Spread(p);int mid=(a[p].l+a[p].r)/2,ans=-1e9;if(l<=mid){ans=max(ans,Ask(p*2,l,r));}if(r>mid){ans=max(ans,Ask(p*2+1,l,r));}a[p].mx=max(a[p*2].mx,a[p*2+1].mx);return ans; } void dfs1(int u,int faa){fa[u]=faa;dep[u]=dep[faa]+1;siz[u]=1;for(int i=hed[u];i;i=nxt[i]){int v=ver[i];if(v==faa){continue;}dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[son[u]]){son[u]=v;}} } void dfs2(int u,int tp){top[u]=tp;dfn[u]=++cnt;idx[cnt]=u;//cout<<u<<" "<<cnt<<endl;if(son[u]){dfs2(son[u],tp);}for(int i=hed[u];i;i=nxt[i]){int v=ver[i];if(v==fa[u]||v==son[u]){continue;}dfs2(v,v);} } int AskMax(int a,int b){int ans=-1e9;while(top[a]!=top[b]){// cout<<a<<b<<endl; if(dep[top[a]]>dep[top[b]]){ans=max(Ask(1,dfn[top[a]],dfn[a]),ans);a=fa[top[a]];continue;}ans=max(Ask(1,dfn[top[b]],dfn[b]),ans);b=fa[top[b]];}//cout<<dfn[a]<<" "<<dfn[b]<<endl;//cout<<ans<<endl;if(dep[a]>dep[b]){ans=max(Ask(1,dfn[b],dfn[a]),ans);return ans;}ans=max(Ask(1,dfn[a],dfn[b]),ans);return ans; } signed main(){ios::sync_with_stdio(0);cin>>n;sm=n;for(int i=1;i<n;i++){int a,b,c;cin>>a>>b>>c;add(a,++sm);add(sm,a);add(b,sm);add(sm,b);w[sm]=c;}dfs1(1,0);dfs2(1,1);Build(1,1,sm);while(1){string opt;int x,t,aa,bb;cin>>opt;/*for(int k=1;k<=n;k++){cout<<a[k].l<<" - "<<a[k].r<<" = "<<a[k].mx<<endl;}*/if(opt=="CHANGE"){cin>>x>>t;Change(1,dfn[n+x],dfn[n+x],t);}if(opt=="QUERY"){cin>>aa>>bb;cout<<AskMax(aa,bb)<<endl;}if(opt=="DONE"){break;}}return 0; }