#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=12;
int n,m,ct,A[N][N],B[N][N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Steiner_Tree{
struct PRE{int i,j,s;PRE(Re I=0,Re J=0,Re S=0){i=I,j=J,s=S;}}pre[N][N][1024+3];
int vis[N][N],dp[N][N][1024+3],wx[4]={-1,0,1,0},wy[4]={0,1,0,-1};
struct QAQ{int x,y;QAQ(Re X=0,Re Y=0){x=X,y=Y;}};
queue<QAQ>Q;
inline void SPFA(Re s){
while(!Q.empty()){
QAQ now=Q.front();Q.pop();
Re x=now.x,y=now.y;vis[x][y]=0;
for(Re o=0;o<4;++o){
Re nx=x+wx[o],ny=y+wy[o];
if(nx<1||nx>n||ny<1||ny>m)continue;
if(dp[nx][ny][s]>dp[x][y][s]+B[nx][ny]){
dp[nx][ny][s]=dp[x][y][s]+B[nx][ny],pre[nx][ny][s]=PRE(x,y,s);
if(!vis[nx][ny])Q.push(QAQ(nx,ny)),vis[nx][ny]=1;
}
}
}
}
int Ans[N][N];
inline void dfs(Re i,Re j,Re s){
Ans[i][j]=1;PRE to=pre[i][j][s];
if(to.s){
dfs(to.i,to.j,to.s);
if(to.i==i&&to.j==j)dfs(to.i,to.j,s^to.s);
}
}
inline void sakura(){
memset(dp,63,sizeof(dp));
Re V=(1<<ct)-1,inf=dp[0][0][0];
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
if(A[i][j])dp[i][j][1<<A[i][j]-1]=0;
for(Re s=0;s<=V;++s){
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j){
for(Re t=(s-1)&s,tmp;t;t=(t-1)&s)
if((tmp=dp[i][j][t]+dp[i][j][s^t]-B[i][j])<dp[i][j][s])
dp[i][j][s]=tmp,pre[i][j][s]=PRE(i,j,t);
if(dp[i][j][s]!=inf)Q.push(QAQ(i,j)),vis[i][j]=1;
}
SPFA(s);
}
Re ans=2e9,x,y;
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
if(A[i][j])ans=dp[x=i][y=j][V];
printf("%d\n",ans);
dfs(x,y,V);
for(Re i=1;i<=n;puts(""),++i)
for(Re j=1;j<=m;++j)
putchar(A[i][j]?'x':(Ans[i][j]?'o':'_'));
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j){
in(B[i][j]);
if(!B[i][j])A[i][j]=++ct;
}
T1.sakura();
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=503;
int n,m,o,x,y,z,K,ans,pan[N],head[N],dp[N][1024+3];queue<int>Q;
struct QAQ{int w,to,next;}a[M<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void SPFA(Re s){
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(dp[x][s]+a[i].w<dp[to=a[i].to][s]){
dp[to][s]=dp[x][s]+a[i].w;
if(!pan[to])Q.push(to),pan[to]=1;
}
}
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(K);
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
memset(dp,63,sizeof(dp));Re inf=dp[0][0];
for(Re i=1;i<=K;++i)in(x),dp[x][1<<i-1]=0,ans=x;
Re V=(1<<K)-1;
for(Re s=0;s<=V;++s){
for(Re i=1;i<=n;++i){
for(Re t=(s-1)&s;t;t=(t-1)&s)
dp[i][s]=min(dp[i][s],dp[i][t]+dp[i][s^t]);
if(dp[i][s]!=inf)Q.push(i),pan[i]=1;
}
SPFA(s);
}
printf("%d ",dp[ans][V]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int o,n,m,x,y,t,tmp,dfn_O,A[N],Q[N],cnt[N],dfn[N],idx[N],size[N],head[N];LL ans,Ans[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void dfs(Re x,Re fa){
idx[dfn[x]=++dfn_O]=x,size[x]=1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dfs(to,x),size[x]+=size[to];
}
inline void CL(){
while(t)cnt[Q[t--]]=0;ans=tmp=0;
}
inline void insert(Re x){
++cnt[Q[++t]=A[x]];
if(cnt[A[x]]>tmp)tmp=cnt[ans=A[x]];
else if(cnt[A[x]]==tmp)ans+=A[x];
}
inline void sakura(Re L,Re R){
if(L==R){if(size[idx[L]]==1)Ans[idx[L]]=A[idx[L]];return;}
Re mid=L+R>>1;
sakura(L,mid),sakura(mid+1,R);
Re p=mid;CL();
for(Re i=mid,j;i>=L&&(j=i+size[idx[i]]-1)<=R;--i){
insert(idx[i]);
if(j<=mid)continue;
while(p<j)insert(idx[++p]);
Ans[idx[i]]=ans;
}
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs(1,0),sakura(1,n);
for(Re i=1;i<=n;++i)printf("%lld ",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int o,n,m,x,y,t,K,tmp,A[N],Q[N],cnt[N],son[N],size[N],head[N];LL ans,Ans[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void dfs(Re x,Re fa){
size[x]=1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x),size[x]+=size[to];
if(size[to]>size[son[x]])son[x]=to;
}
}
inline void CL(){
while(t)cnt[Q[t--]]=0;ans=tmp=0;
}
inline void insert(Re x){
++cnt[Q[++t]=A[x]];
if(cnt[A[x]]>tmp)tmp=cnt[ans=A[x]];
else if(cnt[A[x]]==tmp)ans+=A[x];
}
inline void addson(Re x,Re fa){
insert(x);
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)addson(to,x);
}
inline void sakura(Re x,Re fa){
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa&&to!=son[x])sakura(to,x),CL();
if(son[x])sakura(son[x],x);
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa&&to!=son[x])addson(to,x);
insert(x),Ans[x]=ans;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs(1,0),sakura(1,0);
for(Re i=1;i<=n;++i)printf("%lld ",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e6+3;
int n,op,fa[N],pf[N],son[N];LL ans;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline LL get_prufer(){
for(Re i=1;i<=n-1;++i)in(fa[i]),++son[fa[i]];
for(Re i=1,j=1;i<=n-2;++i,++j){
while(son[j])++j;pf[i]=fa[j];
while(i<=n-2&&!--son[pf[i]]&&pf[i]<j)pf[i+1]=fa[pf[i]],++i;
}
// printf("Prufer: ");for(Re i=1;i<=n-2;++i)printf("%d ",pf[i]);puts("");
for(Re i=1;i<=n-2;++i)ans^=(LL)i*pf[i];
return ans;
}
inline LL get_fa(){
for(Re i=1;i<=n-2;++i)in(pf[i]),++son[pf[i]];pf[n-1]=n;
for(Re i=1,j=1;i<=n-1;++i,++j){
while(son[j])++j;fa[j]=pf[i];
while(i<=n-1&&!--son[pf[i]]&&pf[i]<j)fa[pf[i]]=pf[i+1],++i;
}
// printf("fa: ");for(Re i=1;i<=n-1;++i)printf("%d ",fa[i]);puts("");
for(Re i=1;i<=n-1;++i)ans^=(LL)i*fa[i];
return ans;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(op),printf("%lld\n",op<2?get_prufer():get_fa());
}
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#define Re register int
const int N=1e6+3;
#define LL long long
int n,m,x,y,o=1,h,t,st,cnt,In[N],cir[N],pan[N],head[N];LL ans,tmp,Q[N<<1],S[N<<1],dp[N<<1],dis[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline LL max(LL a,LL b){return a>b?a:b;}
inline int find_circle(Re x,Re p){
if(In[x]){st=x,cir[++cnt]=x,pan[x]=1;return 1;}
In[x]=1;
for(Re i=head[x];i;i=a[i].next)
if(i!=(p^1)&&find_circle(a[i].to,i)){
pan[x]=1;
if(x==st){S[0]=S[1]-a[i].w;return 0;}
cir[++cnt]=x,S[cnt]=S[cnt-1]+a[i].w;
return 1;
}
return 0;
}
inline void Tree_dp(Re x){
pan[x]=1;
for(Re i=head[x],to;i;i=a[i].next)
if(!pan[to=a[i].to]){
Tree_dp(to);
tmp=max(tmp,dis[x]+a[i].w+dis[to]);
dis[x]=max(dis[x],dis[to]+a[i].w);
}
}
inline LL pp(Re j){return dp[j]-S[j];}
inline LL sakura(Re root){
S[0]=cnt=st=0;find_circle(root,0);
LL ans1=0,ans2=0;tmp=0;
for(Re i=1;i<=cnt;++i){
tmp=0,Tree_dp(cir[i]),ans1=max(ans1,tmp);
dp[i+cnt]=dp[i]=dis[cir[i]];
S[i+cnt]=S[i+cnt-1]+S[i]-S[i-1];
}
h=1,t=0,Q[++t]=1;//ans=max(dp[i]+dp[j]+S[i]-S[j]) i-j+1<=cnt i-cnt+1<=j<i
for(Re i=2;i<=(cnt<<1);++i){
while(h<=t&&Q[h]<i-cnt+1)++h;
if(h<=t)ans2=max(ans2,dp[i]+S[i]+pp(Q[h]));
while(h<=t&&pp(Q[t])<=pp(i))--t;
Q[++t]=i;
}
return max(ans1,ans2);
}
int main(){
in(n);
for(Re i=1;i<=n;++i)in(x),in(y),add(i,x,y),add(x,i,y);
for(Re i=1;i<=n;++i)if(!pan[i])ans+=sakura(i);
printf("%lld",ans);
}#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=5e5+3;
int n,m,x,y,T,root;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
int Q[N];
struct QAQ{int fa,tag,ps[2];}tr[N];
inline void pushup(Re p){}
inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl);
if(pr)updata(pr);
tr[p].tag=0;
}
}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
pushup(fa),pushup(p);
}
inline void splay(Re p){
Re x=p,t=0;Q[++t]=x;
while(nort(x))Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline int access(Re p){
Re son=0;
for(;p;son=p,p=pf)
splay(p),pr=son,pushup(p);
return son;
}
inline void makeroot(Re p){access(p),splay(p),updata(p);}
inline int findroot(Re p){
access(p),splay(p),pushdown(p);
while(pl)pushdown(p=pl);
return p;
}
inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
inline void link(Re x,Re y){makeroot(x),tr[x].fa=y;}
inline void cut(Re x,Re y){
makeroot(x);
if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
tr[x].fa=tr[y].ps[0]=0,pushup(y);
}
inline int lca(Re x,Re y){access(x);return access(y);}
}LCT;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),in(root),m=n-1;
while(m--)in(x),in(y),LCT.link(x,y);LCT.makeroot(root);
while(T--)in(x),in(y),printf("%d\n",LCT.lca(x,y));
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3,logN=20;
int n,m,o,x,y,T,rt,head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct LCA{
int O,lg[N<<1],Qx[N<<1],Qd[N<<1],fir[N],deep[N],f[N<<1][23],ans[N<<1][23];
inline void dfs(Re x,Re fa){
Qx[fir[x]=++O]=x,Qd[O]=deep[x]=deep[fa]+1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dfs(to,x),Qx[++O]=x,Qd[O]=deep[x];
}
inline void build(Re rt){
dfs(rt,0),lg[0]=-1;
for(Re i=1;i<=O;++i)f[i][0]=Qd[i],ans[i][0]=Qx[i],lg[i]=lg[i>>1]+1;
for(Re j=1;j<=logN;++j)
for(Re i=1;i+(1<<j)-1<=O;++i)
if(f[i][j-1]<f[i+(1<<j-1)][j-1])f[i][j]=f[i][j-1],ans[i][j]=ans[i][j-1];
else f[i][j]=f[i+(1<<j-1)][j-1],ans[i][j]=ans[i+(1<<j-1)][j-1];
}
inline int lca(Re x,Re y){
Re L=fir[x],R=fir[y];
if(L>R)swap(L,R);
Re m=lg[R-L+1];
return f[L][m]<f[R-(1<<m)+1][m]?ans[L][m]:ans[R-(1<<m)+1][m];
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),in(rt),m=n-1;
while(m--)in(x),in(y),add(x,y),add(y,x);
T1.build(rt);
while(T--)in(x),in(y),printf("%d\n",T1.lca(x,y));
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5e5+3,M=5e5+3,logN=19;
int T,Q,n,m,x,y,o,root,head[N];
struct QAQ{int to,next;}a[M<<1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct LCA{
int deep[N],ant[N][23];
inline void dfs(Re x,Re fa){
deep[x]=deep[ant[x][0]=fa]+1;
for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
}
inline int lca(Re x,Re y){
if(deep[x]<deep[y])swap(x,y);
for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])x=ant[x][i];
if(x==y)return x;
for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])x=ant[x][i],y=ant[y][i];
return ant[x][0];
}
}T1;
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
int main(){
in(n),in(Q),in(root),m=n-1;
while(m--)in(x),in(y),add(x,y),add(y,x);
T1.dfs(root,0);
while(Q--)in(x),in(y),printf("%d\n",T1.lca(x,y));
}
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5e5+3;
int n,m,x,y,T,root;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Killed_Tree{
struct QAQ{int to,next;}a[N<<1];
int o,head[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
int id_o,id[N],fa[N],son[N],top[N],deep[N],size[N];
inline void dfs1(Re x,Re Fa){
size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=Fa){
dfs1(to,x);
size[x]+=size[to];
if(size[to]>size[son[x]])son[x]=to;
}
}
inline void dfs2(Re x,Re rt){
id[x]=++id_o,top[x]=rt;
if(!son[x])return;
dfs2(son[x],rt);
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
}
inline void kill(Re rt){dfs1(rt,0),dfs2(rt,rt);}
inline int lca(Re x,Re y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
return x;
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),in(root),m=n-1;
while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
T1.kill(root);
while(T--)in(x),in(y),printf("%d\n",T1.lca(x,y));
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1e4+3,M=3e5+3;
int n,m,x,y,o,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
struct Tree_Diam_DFS{
int cur,dis[N];
inline void dfs(Re x,Re fa){
if(dis[x]>dis[cur])cur=x;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dis[to]=dis[x]+a[i].w,dfs(to,x);
}
inline int sakura(){
dfs(1,0);
memset(dis,0,sizeof(dis));
dfs(cur,0);
return dis[cur];
}
}T1;
int main(){
in(n),m=n-1;
while(m--)in(x),in(y),add(x,y,1),add(y,x,1);
printf("%d\n",T1.sakura());
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1e4+3,M=3e5+3;
int n,m,x,y,o,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
struct Tree_Diam_DP1{
int ans,dis[N];
inline void dfs(Re x,Re fa){
for(Re i=head[x],to,tmp;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x);
ans=max(ans,dis[x]+dis[to]+a[i].w);
dis[x]=max(dis[x],dis[to]+a[i].w);
}
}
inline int sakura(){dfs(1,0);return ans;}
}T1;
struct Tree_Diam_DP2{
int ans,dis[N][2];
inline void dfs(Re x,Re fa){
for(Re i=head[x],to,tmp;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x);
if(dis[x][0]<(tmp=dis[to][0]+a[i].w))dis[x][1]=dis[x][0],dis[x][0]=tmp;
else dis[x][1]=max(dis[x][1],tmp);
}
ans=max(ans,dis[x][1]+dis[x][0]);
}
inline int sakura(){dfs(1,0);return ans;}
}T2;
int main(){
in(n),m=n-1;
while(m--)in(x),in(y),add(x,y,1),add(y,x,1);
printf("%d\n",T1.sakura());
// printf("%d\n",T2.sakura());
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=2e4+3,inf=2e9;
int n,m,x,y,o,T,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
struct Tree_Diam_DP1{
int ans,dp[N],size[N];
inline void dfs(Re x,Re fa){
size[x]=1,dp[x]=0;
for(Re i=head[x],to,tmp;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x),size[x]+=size[to];
dp[x]=max(dp[x],size[to]);
}
if(n-size[x])dp[x]=max(dp[x],n-size[x]);
}
inline void sakura(){
dfs(1,0),dp[ans=0]=inf;
for(Re i=1;i<=n;++i)if(dp[i]<dp[ans])ans=i;
}
}T1;
int main(){
in(T);
while(T--){
memset(head,0,sizeof(head));
in(n),m=n-1,o=0;
while(m--)in(x),in(y),add(x,y,1),add(y,x,1);
T1.sakura();
printf("%d %d\n",T1.ans,T1.dp[T1.ans]);
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=17;
int n,m,x,y,o,T,dfn_o,dfn[N],deep[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct LCA{
int ant[N][20];
inline void dfs(Re x,Re fa){
deep[x]=deep[ant[x][0]=fa]+1,dfn[x]=++dfn_o;
for(Re j=1;(1<<j)<=deep[x];++j)ant[x][j]=ant[ant[x][j-1]][j-1];
for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
}
inline int lca(Re x,Re y){
if(deep[x]<deep[y])swap(x,y);
for(Re j=logN;j>=0;--j)if(deep[ant[x][j]]>=deep[y])x=ant[x][j];
if(x==y)return x;
for(Re j=logN;j>=0;--j)if(ant[x][j]!=ant[y][j])x=ant[x][j],y=ant[y][j];
return ant[x][0];
}
}T1;
inline bool cmp(Re x,Re y){return dfn[x]<dfn[y];}
struct Virtual_Tree{
int t,o,ans,A[N],Q[N],key[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void insert(Re x){// 撤销操作
Re lca=T1.lca(Q[t],x);
while(t>1&&deep[Q[t-1]]>deep[lca])add(Q[t-1],Q[t]),--t;
if(t&&deep[Q[t]]>deep[lca])add(lca,Q[t--]);
if(!t||Q[t]!=lca)Q[++t]=lca;
Q[++t]=x;
}
inline void dfs(Re x){// 撤销操作
if(key[x])
for(Re i=head[x],to;i;i=a[i].next){
dfs(to=a[i].to);
if(key[to])key[to]=0,++ans;
}
else{
for(Re i=head[x],to;i;i=a[i].next)
dfs(to=a[i].to),key[x]+=key[to],key[to]=0;
if(key[x]>1)key[x]=0,++ans;
}
head[x]=0;
}
inline void sakura(){
in(m);Re flag=1;ans=o=t=0;
for(Re i=1;i<=m;++i)in(A[i]),key[A[i]]=1;
for(Re i=1;i<=m&&flag;++i)flag&=(!key[T1.ant[A[i]][0]]);
if(!flag){
for(Re i=1;i<=m;++i)key[A[i]]=0;
puts("-1");return;
}
sort(A+1,A+m+1,cmp),Q[++t]=1;
for(Re i=1+(A[1]==1);i<=m;++i)insert(A[i]);
while(t>1)add(Q[t-1],Q[t]),--t;
dfs(1),key[1]=0;
printf("%d\n",ans);
}
}T2;
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1;
while(m--)in(x),in(y),add(x,y),add(y,x);
T1.dfs(1,0),in(T);
while(T--)T2.sakura();
}
#include<algorithm>
#include<cstdio>
#define pl tr[p].lp
#define pr tr[p].rp
#define mid (L+R>>1)
#define Re register int
const int N=3e5+3,logN=19;
int x,y,n,m,T,o,lca,w[N],pt[N],ans[N],head[N],deep[N];
struct QWQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
struct Segmemt_Tree{
struct QAQ{int g,lp,rp;}tr[N*36];int cnt;
inline void change(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++cnt;
if(L==R){tr[p].g+=v;return;}
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
}
inline int merge(Re p,Re q){
if(!p)return q;if(!q)return p;
tr[p].g+=tr[q].g;
pl=merge(pl,tr[q].lp);
pr=merge(pr,tr[q].rp);
return p;
}
inline int ask(Re p,Re L,Re R,Re x){
if(!p)return 0;
if(L==R)return tr[p].g;
if(x<=mid)return ask(pl,L,mid,x);
else return ask(pr,mid+1,R,x);
}
}T1;
struct LCA{
int ant[N][23];
inline void dfs(Re x,Re fa){
deep[x]=deep[fa]+1,ant[x][0]=fa;
for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
}
inline int lca(Re x,Re y){
if(deep[x]>deep[y])std::swap(x,y);
for(Re i=logN;i>=0;--i)if(deep[x]<=deep[y]-(1<<i))y=ant[y][i];
if(x==y)return y;
for(Re i=logN;i>=0;--i)
if(ant[x][i]==ant[y][i])continue;
else x=ant[x][i],y=ant[y][i];
return ant[x][0];
}
}T2;
inline void dfs(Re x,Re fa){
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)
dfs(to,x),pt[x]=T1.merge(pt[x],pt[to]);
ans[x]+=T1.ask(pt[x],1,n<<1,n+deep[x]-w[x]);
if(w[x]&&deep[x]+w[x]<=n)ans[x]+=T1.ask(pt[x],1,n<<1,n+deep[x]+w[x]);
}
int main(){
in(n),in(T),m=n-1;
while(m--)in(x),in(y),add(x,y),add(y,x);
for(Re i=1;i<=n;++i)in(w[i]);
T2.dfs(1,0);
while(T--){
in(x),in(y),lca=T2.lca(x,y);
T1.change(pt[x],1,n<<1,n+deep[x],1);
T1.change(pt[y],1,n<<1,n+deep[lca]*2-deep[x],1);
T1.change(pt[lca],1,n<<1,n+deep[x],-1);
T1.change(pt[T2.ant[lca][0]],1,n<<1,n+deep[lca]*2-deep[x],-1);
}
dfs(1,0);
for(Re i=1;i<=n;++i)printf("%d ",ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
int n,b,c,d,t,longson[10005],d1[10005],d2[10005],df[10005],head[10005];
struct QAQ{int to,next,w;}a[20005];
inline void add(int x,int y,int w){a[++t].to=y,a[t].w=w,a[t].next=head[x],head[x]=t;}
inline void dfs(int x,int pa){
for(R i=head[x];i;i=a[i].next){
R s,to=a[i].to;
if(to==pa)continue;
dfs(to,x);s=d1[to]+a[i].w;
if(s>d1[x])d2[x]=d1[x],d1[x]=s,longson[x]=to;
else d2[x]=max(d2[x],s);
}
}
inline void dfsf(int x,int pa){
for(R i=head[x];i;i=a[i].next){
R to=a[i].to;
if(to==pa)continue;
if(longson[x]==to)df[to]=a[i].w+max(d2[x],df[x]);
else df[to]=a[i].w+max(d1[x],df[x]);
dfsf(to,x);
}
}
inline int sakura(){
while(~scanf("%d",&n)){
memset(longson,0,sizeof(longson));
memset(head,0,sizeof(head));
memset(d1,0,sizeof(d1));
memset(d2,0,sizeof(d2));
memset(df,0,sizeof(df));
memset(a,0,sizeof(a));t=0;
for(R i=2;i<=n;i++){
scanf("%d%d",&b,&c);
add(i,b,c),add(b,i,c);
}
dfs(1,0);dfsf(1,0);
for(R i=1;i<=n;i++)printf("%d\n",max(d1[i],df[i]));
}
return 0;
}
int QAQWQ=sakura();
int main(){}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+5,logN=14;
int o,n,m,x,y,t,T,dfn_O,A[N],Q[N],dfn[N],idx[N],Ans[N],cnt[N],son[N],deep[N],size[N],head[N];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
struct Query{
int o,head[N];
struct QAQ{int to,id,next;}a[N];
inline void add(Re x,Re y,Re id){a[++o].to=y,a[o].id=id,a[o].next=head[x],head[x]=o;}
}QT;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct LCA{
int ant[N][15];
inline void dfs(Re x,Re fa){
deep[x]=deep[ant[x][0]=fa]+1;
for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
}
inline int kant(Re x,Re k){
for(Re i=logN;i>=0;--i)
if((1<<i)<=k)k-=(1<<i),x=ant[x][i];
return x;
}
}T1;
inline void dfs(Re x,Re fa){
idx[dfn[x]=++dfn_O]=x,size[x]=1,deep[x]=deep[fa]+1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dfs(to,x),size[x]+=size[to];
}
inline void CL(){
while(t)cnt[Q[t--]]=0;
}
inline void insert(Re x){
++cnt[Q[++t]=deep[x]];
}
inline void addson(Re x,Re fa){
insert(x);
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)addson(to,x);
}
inline void getans(Re x){
for(Re i=QT.head[x];i;i=QT.a[i].next)
Ans[QT.a[i].id]=cnt[deep[x]+QT.a[i].to];
}
inline void sakura(Re L,Re R){
if(L==R){if(size[idx[L]]==1)CL(),insert(idx[L]),getans(idx[L]);return;}
Re mid=L+R>>1;
sakura(L,mid),sakura(mid+1,R);
Re p=mid;CL();
for(Re i=mid,j;i>=L&&(j=i+size[idx[i]]-1)<=R;--i){
insert(idx[i]);
if(j<=mid)continue;
while(p<j)insert(idx[++p]);
getans(idx[i]);
}
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=2;i<=n;++i)in(x),add(x,i);
T1.dfs(1,0);
for(Re i=1;i<=T;++i)in(x),in(y),QT.add(T1.kant(x,y),y,i);
dfs(1,0),sakura(1,n);
for(Re i=1;i<=T;++i)printf("%d ",max(Ans[i]-1,0));
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+5,logN=14;
int o,n,m,x,y,t,T,A[N],Q[N],Ans[N],cnt[N],son[N],deep[N],size[N],head[N];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
struct Query{
int o,head[N];
struct QAQ{int to,id,next;}a[N];
inline void add(Re x,Re y,Re id){a[++o].to=y,a[o].id=id,a[o].next=head[x],head[x]=o;}
}QT;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct LCA{
int ant[N][15];
inline void dfs(Re x,Re fa){
deep[x]=deep[ant[x][0]=fa]+1;
for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
}
inline int kant(Re x,Re k){
for(Re i=logN;i>=0;--i)
if((1<<i)<=k)k-=(1<<i),x=ant[x][i];
return x;
}
}T1;
inline void dfs(Re x,Re fa){
size[x]=1,deep[x]=deep[fa]+1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x),size[x]+=size[to];
if(size[to]>size[son[x]])son[x]=to;
}
}
inline void CL(){
while(t)cnt[Q[t--]]=0;
}
inline void insert(Re x){
++cnt[Q[++t]=deep[x]];
}
inline void addson(Re x,Re fa){
insert(x);
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)addson(to,x);
}
inline void sakura(Re x,Re fa){
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa&&to!=son[x])sakura(to,x),CL();
if(son[x])sakura(son[x],x);
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa&&to!=son[x])addson(to,x);
insert(x);
for(Re i=QT.head[x];i;i=QT.a[i].next)
Ans[QT.a[i].id]=cnt[deep[x]+QT.a[i].to];
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=2;i<=n;++i)in(x),add(x,i);
T1.dfs(1,0);
for(Re i=1;i<=T;++i)in(x),in(y),QT.add(T1.kant(x,y),y,i);
dfs(1,0),sakura(1,n);
for(Re i=1;i<=T;++i)printf("%d ",max(Ans[i]-1,0));
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
int n,m,x,y,o,T,op,A[N],co[N],fa[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Queue{
priority_queue<int>Q,D;
inline void insert(Re x){Q.push(x);}
inline void erase(Re x){if(Q.top()==x)Q.pop();else D.push(x);}
inline int top(){
while(!Q.empty()&&!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
return Q.empty()?-inf:Q.top();
}
};
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
struct QAQ{int fa,max,ps[2];}tr[N];Queue si[N];
inline void pushup(Re p){
tr[p].max=max(max(A[p],si[p].top()),max(tr[pl].max,tr[pr].max));
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
pushup(fa),pushup(p);
}
inline void splay(Re p){
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline void access(Re p){
for(Re son=0;p;son=p,p=pf)
splay(p),si[p].insert(tr[pr].max),pr=son,si[p].erase(tr[pr].max),pushup(p);
}
inline void link(Re p,Re fa){
access(p),splay(p),access(fa),splay(fa),si[pf=fa].insert(tr[p].max),pushup(fa);
}
inline void cut(Re p,Re fa){
access(p),splay(p),splay(fa),pf=tr[fa].ps[1]=0,pushup(fa);
}
inline int ask(Re p){
access(p),splay(p);while(pl)p=pl;splay(p);return tr[pr].max;
}
inline void change(Re p,Re v){
access(p),splay(p),A[p]=v,pushup(p);
}
}LCT[2];
inline void dfs(Re x,Re Fa){
LCT[0].tr[x].max=LCT[1].tr[x].max=A[x];
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=Fa)dfs(to,x);
LCT[co[x]].link(x,fa[x]=Fa);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1,LCT[0].tr[0].max=LCT[1].tr[0].max=-inf;
while(m--)in(x),in(y),add(x,y),add(y,x);
for(Re i=1;i<=n;++i)in(co[i]);
for(Re i=1;i<=n;++i)in(A[i]);
in(T),dfs(1,n+1);
while(T--){
in(op),in(x);
if(op<1)printf("%d\n",LCT[co[x]].ask(x));
else if(op<2)LCT[co[x]].cut(x,fa[x]),LCT[co[x]^=1].link(x,fa[x]);
else in(y),LCT[co[x]].change(x,y);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e6+3,M=2e6+3;
int n,m,x,y,T,op,HYJ,Ans,root,A[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
int Q[N];
struct QAQ{int fa,si,ans,tag,shi,yuan,ps[2];}tr[N];
inline void pushup(Re p){
tr[p].shi=A[p]^tr[pl].shi^tr[pr].shi;
tr[p].ans=A[p]^tr[p].si^tr[pl].ans^tr[pr].ans;
}
inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl);
if(pr)updata(pr);
tr[p].tag=0;
}
}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
pushup(fa),pushup(p);
}
inline void splay(Re p){
Re x=p,t=0;Q[++t]=x;
while(nort(x))Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline int access(Re p){
Re son=0;
for(;p;son=p,p=pf)
splay(p),tr[p].si^=tr[pr].ans,tr[p].si^=tr[pr=son].ans,pushup(p);
return son;
}
inline void makeroot(Re p){access(p),splay(p),updata(p);}
inline int findroot(Re p){
access(p),splay(p),pushdown(p);
while(pl)pushdown(p=pl);
return p;
}
inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
inline void link(Re x,Re y){
makeroot(x);
if(findroot(y)!=x)tr[tr[x].fa=y].si^=tr[x].ans,pushup(y);
}
inline int lca(Re x,Re y){access(x);return access(y);}
inline int ask_son(Re p){access(p);return tr[pr].ans^tr[p].si^A[p];}
}LCT;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(HYJ),in(T),m=n-1,T+=HYJ,root=1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),LCT.link(x,y);
LCT.makeroot(root);
// Ans=0;for(Re i=1;i<=n;++i)Ans^=LCT.ask_son(i);
// printf("%d\n",Ans);return 0;
while(T--){
in(op),in(x);
// if(op<2)LCT.makeroot(root=x),printf("%d\n",Ans);
if(op<2){
LCT.makeroot(root=x);Ans=0;
for(Re i=1;i<=n;++i)Ans^=LCT.ask_son(i);
printf("%d\n",Ans);
}
else if(op<3)in(y),LCT.access(x),LCT.splay(x),A[x]=y,LCT.pushup(x);
else if(op<4)in(y),printf("%d\n",LCT.lca(x,y));
else if(op<5)in(y),LCT.split(x,y),printf("%d\n",LCT.tr[y].shi),LCT.makeroot(root);
else printf("%d\n",LCT.ask_son(x));
LCT.makeroot(root);
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+3;
int n,x,y,T,op,a[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
int Q[N];
struct QAQ{int fa,ans,tag,ps[2];}tr[N];
inline void pushup(Re p){
tr[p].ans=a[p]^tr[pl].ans^tr[pr].ans;
}
inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl);
if(pr)updata(pr);
tr[p].tag=0;
}
}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
pushup(fa),pushup(p);
}
inline void splay(Re p){
Re x=p,t=0;Q[++t]=x;
while(nort(x))Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline void access(Re p){
for(Re son=0;p;son=p,p=pf)
splay(p),pr=son,pushup(p);
}
inline void makeroot(Re p){access(p),splay(p),updata(p);}
inline int findroot(Re p){
access(p),splay(p),pushdown(p);
while(pl)pushdown(p=pl);
return p;
}
inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
inline void link(Re x,Re y){makeroot(x);if(findroot(y)!=x)tr[x].fa=y;}
inline void cut(Re x,Re y){
makeroot(x);
if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
tr[x].fa=tr[y].ps[0]=0,pushup(y);
}
}LCT;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)in(a[i]);
while(T--){
in(op),in(x),in(y);
if(!op)LCT.split(x,y),printf("%d\n",LCT.tr[y].ans);
else if(op<2)LCT.link(x,y);
else if(op<3)LCT.cut(x,y);
else LCT.splay(x),a[x]=y,LCT.pushup(x);
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Mat Matrix
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
const LL inf=1e18;
int n,m,o,x,y,T,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Matrix{
LL a[3][3];Mat(){a[1][1]=a[1][2]=a[2][1]=a[2][2]=-inf;}
inline Mat operator*(const Mat &O)const{
Mat A;
for(Re i=1;i<=2;++i)
for(Re j=1;j<=2;++j)
for(Re k=1;k<=2;++k)
A.a[i][j]=max(A.a[i][j],a[i][k]+O.a[k][j]);
return A;
}
}G[N];
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
struct QAQ{int fa,ps[2];}tr[N];Mat TR[N];
inline void pushup(Re p){
TR[p]=G[p];
if(pl)TR[p]=TR[pl]*TR[p];
if(pr)TR[p]=TR[p]*TR[pr];
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
pushup(fa),pushup(p);
}
inline void splay(Re p){
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline void access(Re p){
for(Re son=0;p;son=p,p=pf){
splay(p);
if(pr)G[p].a[1][1]+=max(TR[pr].a[1][1],TR[pr].a[2][1]),G[p].a[1][2]=G[p].a[1][1],G[p].a[2][1]+=TR[pr].a[1][1];
pr=son;
if(pr)G[p].a[1][1]-=max(TR[pr].a[1][1],TR[pr].a[2][1]),G[p].a[1][2]=G[p].a[1][1],G[p].a[2][1]-=TR[pr].a[1][1];
pushup(p);
}
}
inline void change(Re x,Re v){access(x),splay(x),G[x].a[2][1]+=v-A[x],A[x]=v,pushup(x);}//��x�ĵ�Ȩ(G[x][1])
inline LL ask(){splay(1);return max(TR[1].a[1][1],TR[1].a[2][1]);}
}T1;
LL g[N][2];
inline void dfs(Re x,Re fa){
g[x][1]=A[x],T1.tr[x].fa=fa;
for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)
dfs(to,x),g[x][0]+=max(g[to][0],g[to][1]),g[x][1]+=g[to][0];
G[x].a[1][1]=G[x].a[1][2]=g[x][0];
G[x].a[2][1]=g[x][1],G[x].a[2][2]=-inf;
T1.pushup(x);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs(1,0);
while(T--)in(x),in(y),T1.change(x,y),printf("%lld\n",T1.ask());
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Mat Matrix
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
const LL inf=1e18;
int n,m,o,x,y,T,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Matrix{
LL a[3][3];Mat(){a[1][1]=a[1][2]=a[2][1]=a[2][2]=-inf;}
inline Mat operator*(const Mat &O)const{
Mat A;
for(Re i=1;i<=2;++i)
for(Re j=1;j<=2;++j)
for(Re k=1;k<=2;++k)
A.a[i][j]=max(A.a[i][j],a[i][k]+O.a[k][j]);
return A;
}
}G[N];
int idx[N];
struct killed_Tree{
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
Mat tr[N<<2];
inline void pushup(Re p){tr[p]=tr[pl]*tr[pr];}
inline void build(Re p,Re L,Re R){
if(L==R){tr[p]=G[idx[L]];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re x,Mat &v){
if(L==R){tr[p]=v;return;}
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
pushup(p);
}
inline Mat ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p];
if(r<=mid)return ask(pl,L,mid,l,r);
else if(l>mid)return ask(pr,mid+1,R,l,r);
else return ask(pl,L,mid,l,r)*ask(pr,mid+1,R,l,r);
}
}TR;
int id_O,fa[N],st[N],ed[N],son[N],top[N],deep[N],size[N];LL f[N][2],g[N][2];
inline void dfs1(Re x,Re Fa){
deep[x]=deep[fa[x]=Fa]+1,size[x]=1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=Fa){
dfs1(to,x),size[x]+=size[to];
if(size[to]>size[son[x]])son[x]=to;
}
}
inline void dfs2(Re x,Re rt){
idx[st[x]=++id_O]=x,ed[rt]=max(ed[rt],id_O),top[x]=rt;
f[x][0]=g[x][0]=0,f[x][1]=g[x][1]=A[x];
if(son[x])dfs2(son[x],rt),f[x][0]+=max(f[son[x]][0],f[son[x]][1]),f[x][1]+=f[son[x]][0];
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa[x]&&to!=son[x]){
dfs2(to,to);
f[x][0]+=max(f[to][0],f[to][1]),f[x][1]+=f[to][0];
g[x][0]+=max(f[to][0],f[to][1]),g[x][1]+=f[to][0];
}
G[x].a[1][1]=G[x].a[1][2]=g[x][0];
G[x].a[2][1]=g[x][1],G[x].a[2][2]=-inf;
}
inline LL ask(){Mat F=TR.ask(1,1,n,st[1],ed[1]);return max(F.a[1][1],F.a[2][1]);}
inline void change(Re x,Re v){//��x�ĵ�Ȩ
G[x].a[2][1]+=v-A[x],A[x]=v;//��G[x][1]
while(x){
Mat F1=TR.ask(1,1,n,st[top[x]],ed[top[x]]);
TR.change(1,1,n,st[x],G[x]);
Mat F2=TR.ask(1,1,n,st[top[x]],ed[top[x]]);
x=fa[top[x]];
G[x].a[1][1]+=max(F2.a[1][1],F2.a[2][1])-max(F1.a[1][1],F1.a[2][1]),G[x].a[1][2]=G[x].a[1][1];
G[x].a[2][1]+=F2.a[1][1]-F1.a[1][1];
}
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),add(x,y),add(y,x);
T1.dfs1(1,0),T1.dfs2(1,1),T1.TR.build(1,1,n);
while(T--)in(x),in(y),T1.change(x,y),printf("%lld\n",T1.ask());
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+3;
int n,x,y,T;char op;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
int Q[N];
struct QAQ{int fa,si,ans,tag,ps[2];}tr[N];
inline void pushup(Re p){
tr[p].ans=1+tr[p].si+tr[pl].ans+tr[pr].ans;
}
inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl);
if(pr)updata(pr);
tr[p].tag=0;
}
}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
pushup(fa),pushup(p);
}
inline void splay(Re p){
Re x=p,t=0;Q[++t]=x;
while(nort(x))Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline void access(Re p){
for(Re son=0;p;son=p,p=pf)
splay(p),tr[p].si+=tr[pr].ans,tr[p].si-=tr[pr=son].ans,pushup(p);
}
inline void makeroot(Re p){access(p),splay(p),updata(p);}
inline int findroot(Re p){
access(p),splay(p),pushdown(p);
while(pl)pushdown(p=pl);
return p;
}
inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
inline void link(Re x,Re y){
makeroot(x);
if(findroot(y)!=x)tr[tr[x].fa=y].si+=tr[x].ans,pushup(y);
}
inline void cut(Re x,Re y){
makeroot(x);
if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
tr[x].fa=tr[y].ps[0]=0,pushup(y);
}
inline int ask(Re x,Re y){split(x,y);return (tr[x].si+1)*(tr[y].si+1);}
}LCT;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
while(T--){
scanf(" %c",&op),in(x),in(y);
if(op=='A')LCT.link(x,y);
if(op=='Q')printf("%d\n",LCT.ask(x,y));
}
}
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,x,y,z,T,P,op,root,A[N],AA[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Killed_Tree{
struct QAQ{int to,next;}a[N<<1];
int o,id_o,fa[N],id[N],idx[N],top[N],son[N],size[N],deep[N],head[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid (L+R>>1)
struct QAQ{int S,l,r,add;}tr[N<<2];
inline void pushdown(Re p){
Re v=tr[p].add;
if(v){
(tr[pl].S+=v*(tr[pl].r-tr[pl].l+1)%P)%=P,(tr[pl].add+=v)%=P;
(tr[pr].S+=v*(tr[pr].r-tr[pr].l+1)%P)%=P,(tr[pr].add+=v)%=P;
tr[p].add=0;
}
}
inline void build(Re p,Re L,Re R){
tr[p].l=L,tr[p].r=R;
if(L==R){tr[p].S=AA[L]%P;return;}
build(pl,L,mid),build(pr,mid+1,R);
tr[p].S=(tr[pl].S+tr[pr].S)%P;
}
inline void change(Re p,Re l,Re r,Re v){
Re L=tr[p].l,R=tr[p].r;
if(l<=L&&R<=r){(tr[p].S+=v*(R-L+1)%P)%=P,(tr[p].add+=v)%=P;return;}
pushdown(p);
if(l<=mid)change(pl,l,r,v);
if(r>mid)change(pr,l,r,v);
tr[p].S=(tr[pl].S+tr[pr].S)%P;
}
inline int ask(Re p,Re l,Re r){
Re L=tr[p].l,R=tr[p].r;
if(l<=L&&R<=r)return tr[p].S;
Re ans=0;pushdown(p);
if(l<=mid)(ans+=ask(pl,l,r))%=P;
if(r>mid)(ans+=ask(pr,l,r))%=P;
return ans;
}
}TR;
inline void dfs1(Re x,Re Fa){
size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=Fa){
dfs1(to,x);
size[x]+=size[to];
if(size[to]>size[son[x]])son[x]=to;
}
}
inline void dfs2(Re x,Re rt){
id[x]=++id_o,idx[id_o]=x,AA[id_o]=A[x],top[x]=rt;
if(!son[x])return;//Ҷ�ڵ�
dfs2(son[x],rt);
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
}
inline void kill(Re rt){dfs1(rt,0),dfs2(rt,rt),TR.build(1,1,n);}
inline int ask_dis(Re x,Re y){
Re ans=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
(ans+=TR.ask(1,id[top[x]],id[x]))%=P;
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
(ans+=TR.ask(1,id[x],id[y]))%=P;
return ans;
}
inline void change_dis(Re x,Re y,Re v){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
TR.change(1,id[top[x]],id[x],v);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
TR.change(1,id[x],id[y],v);
}
inline int ask_son(Re x){
return TR.ask(1,id[x],id[x]+size[x]-1);
}
inline void change_son(Re x,Re v){
TR.change(1,id[x],id[x]+size[x]-1,v);
}
}T1;
int main(){
in(n),in(T),in(root),in(P),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
T1.kill(root);
while(T--){
in(op);
if(op<2)in(x),in(y),in(z),T1.change_dis(x,y,z%P);
else if(op<3)in(x),in(y),printf("%d\n",T1.ask_dis(x,y));
else if(op<4)in(x),in(z),T1.change_son(x,z%P);
else in(x),printf("%d\n",T1.ask_son(x));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,M=1e5+3;
int n,m,x,y,z,T,op,id,id_O,v[N+M],vis[N+M],Ans[M],ID[N][N];
struct Query{int op,x,y;}Q[M];
inline void in(int &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
int Q[N+M];
struct QAQ{int mx,fa,tag,ps[2];}tr[N+M];
inline void pushup(Re p){
tr[p].mx=p;
if(pl&&v[tr[pl].mx]>v[tr[p].mx])tr[p].mx=tr[pl].mx;
if(pr&&v[tr[pr].mx]>v[tr[p].mx])tr[p].mx=tr[pr].mx;
}
inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl);
if(pr)updata(pr);
tr[p].tag=0;
}
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
pushup(fa),pushup(p);
}
inline void splay(Re p){
Re x=p,t=0;Q[++t]=x;
while(nort(x))Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline void access(Re p){
for(Re son=0;p;son=p,p=pf)
splay(p),pr=son,pushup(p);
}
inline void makeroot(Re x){access(x),splay(x),updata(x);}
inline int findroot(Re p){
access(p),splay(p),pushdown(p);
while(pl)pushdown(p=pl);
return p;
}
inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
inline void link(Re x,Re y){makeroot(x);if(findroot(y)!=x)tr[x].fa=y;}
inline void cut(Re x,Re y){
makeroot(x);
if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
tr[x].fa=tr[y].ps[0]=0,pushup(y);
}
inline void MST_link(Re x,Re y,Re id){
makeroot(x);
if(findroot(y)!=x)link(x,id),link(id,y);
else{
split(x,y);Re mx=tr[y].mx;
if(v[id]<v[mx]){
splay(mx);
tr[tr[mx].ps[0]].fa=tr[tr[mx].ps[1]].fa=0;
tr[mx].ps[0]=tr[mx].ps[1]=tr[mx].fa=0;
link(x,id),link(id,y);
}
}
}
inline int MST_path(Re x,Re y){split(x,y);return v[tr[y].mx];}
}LCT;
struct Kruscal{
int fa[N];
struct QAQ{int x,y,z;inline bool operator<(const QAQ &O)const{return z<O.z;}}a[M];
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void sakura(){
for(Re i=1;i<=n;++i)fa[i]=i;
for(Re i=1;i<=m;++i)in(x),in(y),in(z),v[ID[x][y]=ID[y][x]=++id_O+n]=z,a[i]=(QAQ){x,y,z};
for(Re i=1;i<=T;++i)in(op),in(x),in(y),vis[ID[x][y]]|=op>1,Q[i]=(Query){op,x,y};
sort(a+1,a+m+1);
for(Re i=1,t=0;t<n-1&&i<=m;++i)
if(!vis[ID[x=a[i].x][y=a[i].y]]&&find(x)!=find(y))
fa[find(x)]=find(y),++t,LCT.MST_link(x,y,ID[x][y]);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(T),T1.sakura();
for(Re i=T;i>=1;--i){
Re op=Q[i].op,x=Q[i].x,y=Q[i].y;
if(op&1)Ans[++Ans[0]]=LCT.MST_path(x,y);
else LCT.MST_link(x,y,ID[x][y]);
}
for(Re i=Ans[0];i>=1;--i)printf("%d\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
int n,x,y,z,T,op,root,X[N],Y[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
int Q[N];
struct QAQ{int v,fa,si,shi,ans,add,tag,ans0,ps[2];multiset<int>SI;}tr[N];
inline void pushup(Re p){
tr[p].shi=min(pv,min(tr[pl].shi,tr[pr].shi));
tr[p].si=min(*tr[p].SI.begin(),min(tr[pl].si,tr[pr].si));
tr[p].ans=min(tr[p].shi,tr[p].si);
}
inline void updata(Re p){tr[p].tag^=1,swap(pl,pr);}
inline void updata(Re p,Re v){tr[p].add=1,tr[p].shi=pv=v,tr[p].ans=min(tr[p].shi,tr[p].si);}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl);
if(pr)updata(pr);
tr[p].tag=0;
}
if(tr[p].add){
if(pl)updata(pl,pv);
if(pr)updata(pr,pv);
tr[p].add=0;
}
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
pushup(fa),pushup(p);
}
inline void splay(Re p){
Re x=p,t=0;Q[++t]=x;
while(nort(x))Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline void access(Re p){
for(Re son=0;p;son=p,p=pf){
splay(p);
if(pr)tr[p].SI.insert(tr[pr].ans);
pr=son;
if(pr)tr[p].SI.erase(tr[p].SI.lower_bound(tr[pr].ans));
pushup(p);
}
}
inline void makeroot(Re p){access(p),splay(p),updata(p);}
inline void link(Re x,Re y){makeroot(x),access(y),splay(y),tr[tr[x].fa=y].SI.insert(tr[x].ans);}
inline void change(Re x,Re y,Re z){makeroot(x),access(y),splay(y),updata(y,z);}
inline int ask_son(Re p){access(p),splay(p);return min(pv,*tr[p].SI.begin());}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),T1.tr[0].shi=T1.tr[0].si=inf;
for(Re i=1;i<n;++i)in(X[i]),in(Y[i]);
for(Re i=1;i<=n;++i)in(T1.tr[i].v),T1.tr[i].SI.insert(inf),T1.pushup(i);
for(Re i=1;i<n;++i)T1.link(X[i],Y[i]);
in(root),T1.makeroot(root);
while(T--){
in(op),in(x);
if(op<2)T1.makeroot(root=x);
else if(op<3)in(y),in(z),T1.change(x,y,z),T1.makeroot(root);
else printf("%d\n",T1.ask_son(x));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+3;
int n,m,x,y,o,Sz[N],son[N],Ans[N],dep[N],head[N];int *SZ=Sz,*dp[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void dfs1(Re x,Re fa){
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs1(to,x);
if(dep[to]>dep[son[x]])son[x]=to;
}
dep[x]=dep[son[x]]+1;
}
inline void dfs2(Re x,Re fa){
dp[x][0]=1;
if(son[x])dp[son[x]]=dp[x]+1,dfs2(son[x],x),Ans[x]=Ans[son[x]]+1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa&&to!=son[x]){
dp[to]=SZ,SZ+=dep[to],dfs2(to,x);
for(Re j=1;j<=dep[to];++j){
dp[x][j]+=dp[to][j-1];
if(dp[x][j]>dp[x][Ans[x]])Ans[x]=j;
else if(dp[x][j]==dp[x][Ans[x]])Ans[x]=min(Ans[x],j);
}
}
if(dp[x][Ans[x]]==1)Ans[x]=0;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1;
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs1(1,0),dp[1]=SZ,SZ+=dep[1],dfs2(1,0);
for(Re i=1;i<=n;++i)printf("%d\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3,inf=2e9;
int n,m,o,x,y,K,head[N];LL Ans;
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int rt,sum,cnt,tmp[N],dis[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
size[x]=1,maxp[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)
getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
maxp[x]=max(maxp[x],sum-size[x]);
if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa){
if(dis[fa]+1>K)return;
tmp[++cnt]=dis[x]=dis[fa]+1;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)getdis(to,x);
}
inline int calc(Re x,Re d){
Re ans=0;cnt=0,tmp[++cnt]=dis[x]=d;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])getdis(to,x);
sort(tmp+1,tmp+cnt+1);
Re L=cnt+1,R=cnt;
for(Re i=1;i<=cnt&&i<R;++i){
while(tmp[i]+tmp[L-1]>=K)--L;
while(R>=L&&tmp[i]+tmp[R]>K)--R;
if(L<=R&&i<R&&tmp[i]+tmp[L]==K&&tmp[i]+tmp[R]==K)ans+=(R-max(L,i+1)+1);
}
return ans;
}
inline void sakura(Re x){
Re now=sum;vis[x]=1,Ans+=calc(x,0);
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])
Ans-=calc(to,1),sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(K),m=n-1;
while(m--)in(x),in(y),add(x,y),add(y,x);
sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
printf("%lld\n",Ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=18,inf=1e9;
int n,m,x,y,z,o,T,Cnt,A[N],ans[N],head[N];char op;
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct LCA{
int O,lg[N<<1],fir[N],idx[N<<1],idd[N<<1],dis[N],deep[N],f[N<<1][20],ans[N<<1][20];
inline void dfs(Re x,Re fa,Re w){
idx[fir[x]=++O]=x,idd[O]=deep[x]=deep[fa]+1,dis[x]=dis[fa]+w;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dfs(to,x,a[i].w),idx[++O]=x,idd[O]=deep[x];
}
inline void build(Re rt){
dfs(rt,0,0),lg[0]=-1;
for(Re i=1;i<=O;++i)f[i][0]=idd[i],ans[i][0]=idx[i],lg[i]=lg[i>>1]+1;
for(Re j=1;j<=logN;++j)
for(Re i=1;i+(1<<j)-1<=O;++i)
if(f[i][j-1]<f[i+(1<<j-1)][j-1])f[i][j]=f[i][j-1],ans[i][j]=ans[i][j-1];
else f[i][j]=f[i+(1<<j-1)][j-1],ans[i][j]=ans[i+(1<<j-1)][j-1];
}
inline int lca(Re x,Re y){
Re L=fir[x],R=fir[y];
if(L>R)swap(L,R);
Re m=lg[R-L+1];
return f[L][m]<f[R-(1<<m)+1][m]?ans[L][m]:ans[R-(1<<m)+1][m];
}
}T0;
inline int Dis(Re x,Re y){return T0.dis[x]+T0.dis[y]-(T0.dis[T0.lca(x,y)]<<1);}
struct Queue{
priority_queue<int>Q,D;
inline int top(){
while(!Q.empty()&&!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
return Q.empty()?-inf:Q.top();
}
inline int sec(){
Re x=top();if(x==-inf)return x;
Q.pop();Re ans=top();Q.push(x);
return ans;
}
inline void erase(Re x){if(Q.top()==x)Q.pop();else D.push(x);}
inline void insert(Re x){Q.push(x);}
inline int empty(){
while(!Q.empty()&&!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
return Q.empty();
}
}Ans,Q[N],dis[N];
int rt,sum,Fa[N],vis[N],size[N],maxp[N];
inline void getrt(Re x,Re fa){
size[x]=1,maxp[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)
getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
maxp[x]=max(maxp[x],sum-size[x]);
if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re rt){
dis[rt].insert(Dis(x,Fa[rt]));
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,rt);
}
inline void sakura(Re x){
Re now=sum;vis[x]=1,getdis(x,0,x);
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]){
sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0);
Fa[to=rt]=x,sakura(rt),Q[x].insert(dis[to].top());
}
Q[x].insert(0),Ans.insert(ans[x]=max(0,Q[x].top()+Q[x].sec()));
}
inline void insert(Re x){
Ans.erase(ans[x]),Q[x].insert(0),Ans.insert(ans[x]=max(0,Q[x].top()+Q[x].sec()));
for(Re fa=x;Fa[fa];fa=Fa[fa]){
Re pa=Fa[fa];
Ans.erase(ans[pa]);
if(!dis[fa].empty())Q[pa].erase(dis[fa].top());
dis[fa].insert(Dis(x,pa));
Q[pa].insert(dis[fa].top());
Ans.insert(ans[pa]=max(0,Q[pa].top()+Q[pa].sec()));
}
}
inline void erase(Re x){
Ans.erase(ans[x]),Q[x].erase(0),Ans.insert(ans[x]=max(0,Q[x].top()+Q[x].sec()));
for(Re fa=x;Fa[fa];fa=Fa[fa]){
Re pa=Fa[fa];
Ans.erase(ans[pa]);
Q[pa].erase(dis[fa].top());
dis[fa].erase(Dis(x,pa));
if(!dis[fa].empty())Q[pa].insert(dis[fa].top());
Ans.insert(ans[pa]=max(0,Q[pa].top()+Q[pa].sec()));
}
}
inline void change(Re x){
if(A[x])insert(x),A[x]=0,++Cnt;
else erase(x),A[x]=1,--Cnt;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1,Cnt=n;
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
in(T),T0.build(1),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
while(T--){
scanf(" %c",&op);
if(op=='C')in(x),change(x);
else if(!Cnt)puts("They have disappeared.");
else printf("%d\n",Cnt<2?0:Ans.top());
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,INF=1e6+3,inf=2e9;
int n,m,o,x,y,z,K,Ans,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int rt,sum,dd[N],ddd[N],dep[N],Min[INF],tmp[N],dis[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
size[x]=1,maxp[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)
getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
maxp[x]=max(maxp[x],sum-size[x]);
if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re w){
if(dis[fa]+w>K)return;
dd[++dd[0]]=dis[x]=dis[fa]+w,ddd[dd[0]]=dep[x]=dep[fa]+1;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,a[i].w);
}
inline void calc(Re x){
dis[x]=dep[x]=tmp[0]=0,Min[tmp[++tmp[0]]=0]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]){
dd[0]=0,getdis(to,x,a[i].w);
for(Re i=1;i<=dd[0];++i)Ans=min(Ans,ddd[i]+Min[K-dd[i]]);
for(Re i=1;i<=dd[0];++i)Min[dd[i]]=min(Min[dd[i]],ddd[i]),tmp[++tmp[0]]=dd[i];
}
for(Re i=1;i<=tmp[0];++i)Min[tmp[i]]=inf;
}
inline void sakura(Re x){
Re now=sum;vis[x]=1,calc(x);
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])
sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(K),m=n-1;
for(Re i=0;i<=K;++i)Min[i]=inf;
while(m--)in(x),in(y),in(z),++x,++y,add(x,y,z),add(y,x,z);
Ans=inf,sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
printf("%d\n",(Ans==inf)?-1:Ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],deep[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct LCA{
int fa[N],top[N],son[N],size[N];
inline void dfs1(Re x,Re Fa){
size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=Fa){
dfs1(to,x),size[x]+=size[to];
if(size[son[x]]<size[to])son[x]=to;
}
}
inline void dfs2(Re x,Re rt){
top[x]=rt;
if(!son[x])return;
dfs2(son[x],rt);
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
}
inline void build(){dfs1(1,0),dfs2(1,1);}
inline int lca(Re x,Re y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
return x;
}
}T1;
inline int Dis(Re x,Re y){return deep[x]+deep[y]-(deep[T1.lca(x,y)]<<1);}
struct BIT{
int n;vector<int>C;
inline void build(Re N){C.resize((n=N)+1);}
inline void add(Re x,Re v){++x;while(x<=n)C[x]+=v,x+=x&-x;}
inline int ask(Re x){++x,x=min(x,n);Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR1[N],TR2[N];
int rt,sum,fa[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
size[x]=1,maxp[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)
getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
maxp[x]=max(maxp[x],sum-size[x]);
if(maxp[x]<maxp[rt])rt=x;
}
inline void sakura(Re x,Re Fa){
Re now=sum;vis[x]=1,fa[x]=Fa;
TR1[x].build(now/2+1),TR2[x].build(now+1);
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])
sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt,x);
}
inline void change(Re x,Re v){
TR1[x].add(0,v);//subtree(x)
for(Re i=x;fa[i];i=fa[i]){
Re tmp=Dis(x,fa[i]);
TR1[fa[i]].add(tmp,v);
TR2[i].add(tmp,v);
}
}
inline int ask(Re x,Re K){
Re ans=TR1[x].ask(K);//subtree(x)
for(Re i=x;fa[i];i=fa[i]){
Re tmp=Dis(x,fa[i]);if(tmp>K)continue;
ans+=TR1[fa[i]].ask(K-tmp);
ans-=TR2[i].ask(K-tmp);
}
return ans;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),add(x,y),add(y,x);
T1.build(),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt,0);
for(Re i=1;i<=n;++i)change(i,A[i]);
while(T--){
in(op),in(x),in(y),x^=lastans,y^=lastans;
if(op)change(x,y-A[x]),A[x]=y;
else printf("%d\n",lastans=ask(x,y));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],deep[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct LCA{
int fa[N],top[N],son[N],size[N];
inline void dfs1(Re x,Re Fa){
size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=Fa){
dfs1(to,x),size[x]+=size[to];
if(size[son[x]]<size[to])son[x]=to;
}
}
inline void dfs2(Re x,Re rt){
top[x]=rt;
if(!son[x])return;
dfs2(son[x],rt);
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
}
inline void build(){dfs1(1,0),dfs2(1,1);}
inline int lca(Re x,Re y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
return x;
}
}T1;
inline int Dis(Re x,Re y){return deep[x]+deep[y]-(deep[T1.lca(x,y)]<<1);}
int pt[N<<1];
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid (L+R>>1)
int O;
struct QAQ{int S,lp,rp;}tr[N*60];
inline void change(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;
if(L==R){tr[p].S+=v;return;}
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
tr[p].S=tr[pl].S+tr[pr].S;
}
inline int ask(Re p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].S;
Re ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
}TR;
int rt,sum,fa[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
size[x]=1,maxp[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)
getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
maxp[x]=max(maxp[x],sum-size[x]);
if(maxp[x]<maxp[rt])rt=x;
}
inline void sakura(Re x,Re Fa){
Re now=sum;vis[x]=1,fa[x]=Fa;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])
sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt,x);
}
inline void change(Re x,Re v){
TR.change(pt[x],0,n,0,v);
for(Re i=x;fa[i];i=fa[i]){
Re tmp=Dis(x,fa[i]);
TR.change(pt[fa[i]],0,n,tmp,v);
TR.change(pt[i+n],0,n,tmp,v);
}
}
inline int ask(Re x,Re K){
Re ans=TR.ask(pt[x],0,n,0,K);
for(Re i=x;fa[i];i=fa[i]){
Re tmp=Dis(x,fa[i]);if(tmp>K)continue;
ans+=TR.ask(pt[fa[i]],0,n,0,K-tmp);
ans-=TR.ask(pt[i+n],0,n,0,K-tmp);
}
return ans;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),add(x,y),add(y,x);
T1.build(),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt,0);
for(Re i=1;i<=n;++i)change(i,A[i]);
while(T--){
in(op),in(x),in(y),x^=lastans,y^=lastans;
if(op)change(x,y-A[x]),A[x]=y;
else printf("%d\n",lastans=ask(x,y));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct BIT{
int n;vector<int>C;
inline void build(Re N){C.resize((n=N)+1);}
inline void add(Re x,Re v){++x;while(x<=n)C[x]+=v,x+=x&-x;}
inline int ask(Re x){++x,x=min(x,n);Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR1[N],TR2[N];
int rt,sum,gs[N],vis[N],maxp[N],size[N],frt[N][20],fdis[N][20];
inline void getrt(Re x,Re fa){
size[x]=1,maxp[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)
getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
maxp[x]=max(maxp[x],sum-size[x]);
if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re rt,Re fa,Re d){
frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+1);
}
inline void sakura(Re x){
Re now=sum;vis[x]=1,getdis(x,x,0,0);
TR1[x].build(now/2+1),TR2[x].build(now+1);
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])
sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt);
}
inline void change(Re x,Re v){
TR1[x].add(0,v);//subtree(x)
for(Re i=gs[x];i>=2;--i){
Re tmp=fdis[x][i-1];
TR1[frt[x][i-1]].add(tmp,v);
TR2[frt[x][i]].add(tmp,v);
}
}
inline int ask(Re x,Re K){
Re ans=TR1[x].ask(K);//subtree(x)
for(Re i=gs[x];i>=2;--i){
Re tmp=fdis[x][i-1];if(tmp>K)continue;
ans+=TR1[frt[x][i-1]].ask(K-tmp);
ans-=TR2[frt[x][i]].ask(K-tmp);
}
return ans;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),add(x,y),add(y,x);
sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
for(Re i=1;i<=n;++i)change(i,A[i]);
while(T--){
in(op),in(x),in(y),x^=lastans,y^=lastans;
if(op)change(x,y-A[x]),A[x]=y;
else printf("%d\n",lastans=ask(x,y));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int pt[N<<1];
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid (L+R>>1)
int O;
struct QAQ{int S,lp,rp;}tr[N*60];
inline void change(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;
if(L==R){tr[p].S+=v;return;}
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
tr[p].S=tr[pl].S+tr[pr].S;
}
inline int ask(Re p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].S;
Re ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
}TR;
int rt,sum,gs[N],vis[N],maxp[N],size[N],frt[N][20],fdis[N][20];
inline void getrt(Re x,Re fa){
size[x]=1,maxp[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)
getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
maxp[x]=max(maxp[x],sum-size[x]);
if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re rt,Re fa,Re d){
frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+1);
}
inline void sakura(Re x){
Re now=sum;vis[x]=1,getdis(x,x,0,0);
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])
sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt);
}
inline void change(Re x,Re v){
TR.change(pt[x],0,n,0,v);
for(Re i=gs[x];i>=2;--i){
Re tmp=fdis[x][i-1];
TR.change(pt[frt[x][i-1]],0,n,tmp,v);
TR.change(pt[frt[x][i]+n],0,n,tmp,v);
}
}
inline int ask(Re x,Re K){
Re ans=TR.ask(pt[x],0,n,0,K);
for(Re i=gs[x];i>=2;--i){
Re tmp=fdis[x][i-1];if(tmp>K)continue;
ans+=TR.ask(pt[frt[x][i-1]],0,n,0,K-tmp);
ans-=TR.ask(pt[frt[x][i]+n],0,n,0,K-tmp);
}
return ans;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),add(x,y),add(y,x);
sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
for(Re i=1;i<=n;++i)change(i,A[i]);
while(T--){
in(op),in(x),in(y),x^=lastans,y^=lastans;
if(op)change(x,y-A[x]),A[x]=y;
else printf("%d\n",lastans=ask(x,y));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e4+3,M=103,INF=1e7+3,inf=2e9;
int n,m,o,x,y,z,T,maxK,K[M],Ans[M],head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int rt,sum,dd[N],vis[N],tmp[N],dis[N],maxp[N],size[N];bool judge[INF];
inline void getrt(Re x,Re fa){
size[x]=1,maxp[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)
getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
maxp[x]=max(maxp[x],sum-size[x]);
if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re w){
if(dis[fa]+w>maxK)return;
dd[++dd[0]]=dis[x]=dis[fa]+w;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,a[i].w);
}
inline void calc(Re x){
tmp[0]=0,judge[tmp[++tmp[0]]=0]=1;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]){
dis[x]=dd[0]=0,getdis(to,x,a[i].w);
for(Re j=1;j<=dd[0];++j)
for(Re k=1;k<=T;++k)
if(K[k]>=dd[j])Ans[k]|=judge[K[k]-dd[j]];
for(Re j=1;j<=dd[0];++j)judge[tmp[++tmp[0]]=dd[j]]=1;
}
for(Re i=1;i<=tmp[0];++i)judge[tmp[i]]=0;
}
inline void sakura(Re x){
Re now=sum;vis[x]=1,calc(x);
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])
sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),m=n-1;
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
for(Re i=1;i<=T;++i)in(K[i]),maxK=max(maxK,K[i]);
sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
for(Re i=1;i<=T;++i)puts(Ans[i]?"AYE":"NAY");
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=4e4+3,inf=2e9;
int n,m,o,x,y,z,K,head[N];LL Ans;
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int rt,sum,cnt,tmp[N],dis[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
size[x]=1,maxp[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)
getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
maxp[x]=max(maxp[x],sum-size[x]);
if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re w){
if(dis[fa]+w>K)return;
tmp[++cnt]=dis[x]=dis[fa]+w;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,a[i].w);
}
inline int calc(Re x,Re d){
Re ans=0;cnt=0,tmp[++cnt]=dis[x]=d;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])getdis(to,x,a[i].w);
sort(tmp+1,tmp+cnt+1);
Re R=cnt;
for(Re i=1;i<=cnt&&i<R;++i){
while(i<R&tmp[i]+tmp[R]>K)--R;
if(i<R)ans+=(R-(i+1)+1);
}
return ans;
}
inline void sakura(Re x){
Re now=sum;vis[x]=1,Ans+=calc(x,0);
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])
Ans-=calc(to,a[i].w),sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1;
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
in(K);
sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
printf("%lld\n",Ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
int n,m,o,x,y,z,T,root,A[N],head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct TREE{
int o,head[N];
struct QAQ{int rt,to,next;}a[N];
inline void add(Re x,Re y,Re z){a[++o].rt=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
}T0;
int rt,sum,Sv[N],gs[N],vis[N],size[N],maxp[N],frt[N][20],fdis[N][20];LL Sdv1[N],Sdv2[N];
inline void getrt(Re x,Re fa){
size[x]=1,maxp[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)
getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
maxp[x]=max(maxp[x],sum-size[x]);
if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re rt,Re fa,Re d){
if(x!=rt)frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+a[i].w);
}
inline void sakura(Re x){
Re now=sum;vis[x]=1,getdis(x,x,0,0);
for(Re i=head[x],to;i;i=a[i].next)
if(!vis[to=a[i].to])
sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),T0.add(x,to,rt),sakura(rt);
}
inline void change(Re x,Re v){
Sdv1[x]+=v*0,Sv[x]+=v;
for(Re i=gs[x];i>=2;--i){
Re tmp=fdis[x][i-1];
Sdv1[frt[x][i-1]]+=(LL)v*tmp;
Sdv2[frt[x][i]]+=(LL)v*tmp;
Sv[frt[x][i-1]]+=v;
}
}
inline LL ask(Re x){
LL ans=Sdv1[x];
for(Re i=gs[x];i>=2;--i){
Re tmp=fdis[x][i-1];
ans+=Sdv1[frt[x][i-1]];
ans-=Sdv2[frt[x][i]];
ans+=(LL)(Sv[frt[x][i-1]]-Sv[frt[x][i]])*tmp;
}
return ans;
}
inline LL find(Re x){
LL tmp=ask(x);
for(Re i=T0.head[x];i;i=T0.a[i].next)
if(ask(T0.a[i].to)<tmp)return find(T0.a[i].rt);
return tmp;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),m=n-1;
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(root=rt);
for(Re i=1;i<=n;++i)frt[i][++gs[i]]=i;
while(T--)in(x),in(y),change(x,y),printf("%lld\n",find(root));
}