#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1e5 + 5;
const int LOG = 20; // 2^20 > 1e5
vector<int> adj[MAXN];
vector<int> ch[MAXN];
int depth[MAXN];
int parent[MAXN][LOG];
int n, m, root;
// 预处理:计算每个节点的深度和2^k级祖先
void dfs(int u, int p) {
depth[u] = depth[p] + 1;
parent[u][0] = p;
for (int k = 1; k < LOG; ++k) {
parent[u][k] = parent[parent[u][k-1]][k-1];
}
for (int v : adj[u]) {
if (v != p) {
ch[u].push_back(v);
dfs(v, u);
}
}
}
// 查找u和v的最近公共祖先
int lca(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
// 将u提到与v同一深度
for (int k = LOG - 1; k >= 0; --k) {
if (depth[u] - (1 << k) >= depth[v]) {
u = parent[u][k];
}
}
if (u == v) {
return u;
}
// 同时向上跳
for (int k = LOG - 1; k >= 0; --k) {
if (parent[u][k] != parent[v][k]) {
u = parent[u][k];
v = parent[v][k];
}
}
return parent[u][0];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
root = 1;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// 预处理
dfs(root, 0);
// lca查询
// cout << lca(u, v);
return 0;
}const int MAXN = 1e5 + 5; // 最大节点数
int N, M, R, P; // 节点数、操作数、根节点、模数
vector<int> adj[MAXN]; // 邻接表存储树结构
int val[MAXN]; // 节点初始权值
// 树链剖分相关变量
int parent[MAXN]; // 父节点
int depth[MAXN]; // 节点深度
int sz[MAXN]; // 子树大小
int heavy[MAXN]; // 重儿子
int pos[MAXN]; // 节点在线段树中的位置
int top[MAXN]; // 所在重链的顶部节点
int current_pos; // 当前DFS序位置
// 线段树节点结构
struct node {
int data; // 节点值
int lazy; // 懒标记
node() : data(0), lazy(0) {}
};
vector<node> tree; // 线段树
// 构建线段树
void build(const vector<int>& datas, vector<node>& tree, int rt, int left, int right) {
if (left == right) {
tree[rt].data = datas[left];
return;
}
int mid = left + (right - left) / 2;
build(datas, tree, 2 * rt, left, mid);
build(datas, tree, 2 * rt + 1, mid + 1, right);
tree[rt].data = (tree[2 * rt].data + tree[2 * rt + 1].data) % P;
}
// 下传懒标记
void pushDown(vector<node>& tree, int rt, int len) {
if (tree[rt].lazy != 0) {
tree[rt * 2].data = (tree[rt * 2].data + tree[rt].lazy * (len - len / 2)) % P;
tree[rt * 2].lazy = (tree[rt * 2].lazy + tree[rt].lazy) % P;
tree[rt * 2 + 1].data = (tree[rt * 2 + 1].data + tree[rt].lazy * (len / 2)) % P;
tree[rt * 2 + 1].lazy = (tree[rt * 2 + 1].lazy + tree[rt].lazy) % P;
tree[rt].lazy = 0;
}
}
// 线段树区间查询
int query(vector<node>& tree, int rt, int left, int right, int ql, int qr) {
if (ql > right || qr < left) {
return 0;
}
if (ql <= left && qr >= right) {
return tree[rt].data;
}
pushDown(tree, rt, right - left + 1);
int mid = left + (right - left) / 2;
int leftsum = query(tree, 2 * rt, left, mid, ql, qr);
int rightsum = query(tree, 2 * rt + 1, mid + 1, right, ql, qr);
return (leftsum + rightsum) % P;
}
// 线段树区间更新
void updateRange(vector<node>& tree, int rt, int left, int right, int ul, int ur, int value) {
if (ul > right || ur < left) return;
if (ul <= left && ur >= right) {
tree[rt].data = (tree[rt].data + value * (right - left + 1)) % P;
tree[rt].lazy = (tree[rt].lazy + value) % P;
return;
}
pushDown(tree, rt, right - left + 1);
int mid = left + (right - left) / 2;
updateRange(tree, 2 * rt, left, mid, ul, ur, value);
updateRange(tree, 2 * rt + 1, mid + 1, right, ul, ur, value);
tree[rt].data = (tree[2 * rt].data + tree[2 * rt + 1].data) % P;
}
// 第一次DFS:计算父节点、深度、子树大小和重儿子
void dfs1(int u, int p) {
parent[u] = p;
depth[u] = depth[p] + 1;
sz[u] = 1;
heavy[u] = 0;
for (int v : adj[u]) {
if (v != p) {
dfs1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[heavy[u]]) {
heavy[u] = v;
}
}
}
}
// 第二次DFS:进行重链剖分,计算DFS序和重链顶部
void dfs2(int u, int p, int chain_top) {
pos[u] = ++current_pos;
top[u] = chain_top;
if (heavy[u]) {
dfs2(heavy[u], u, chain_top);
}
for (int v : adj[u]) {
if (v != p && v != heavy[u]) {
dfs2(v, u, v);
}
}
}
// 路径更新:将x到y路径上的节点值都加上z
void pathUpdate(int x, int y, int z) {
while (top[x] != top[y]) {
if (depth[top[x]] > depth[top[y]]) {
swap(x, y);
}
updateRange(tree, 1, 1, N, pos[top[y]], pos[y], z);
y = parent[top[y]];
}
if (depth[x] > depth[y]) {
swap(x, y);
}
updateRange(tree, 1, 1, N, pos[x], pos[y], z);
}
// 路径查询:查询x到y路径上的节点值之和
int pathQuery(int x, int y) {
int res = 0;
while (top[x] != top[y]) {
if (depth[top[x]] > depth[top[y]]) {
swap(x, y);
}
res = (res + query(tree, 1, 1, N, pos[top[y]], pos[y])) % P;
y = parent[top[y]];
}
if (depth[x] > depth[y]) {
swap(x, y);
}
res = (res + query(tree, 1, 1, N, pos[x], pos[y])) % P;
return res;
}
// 子树更新:将以x为根的子树所有节点值加上z
void subtreeUpdate(int x, int z) {
int l = pos[x];
int r = pos[x] + sz[x] - 1;
updateRange(tree, 1, 1, N, l, r, z);
}
// 子树查询:查询以x为根的子树所有节点值之和
int subtreeQuery(int x) {
int l = pos[x];
int r = pos[x] + sz[x] - 1;
return query(tree, 1, 1, N, l, r);
}
// 求两个节点的最近公共祖先(LCA)
int lca(int x, int y) {
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]]) {
swap(x, y);
}
x = parent[top[x]];
}
return depth[x] < depth[y] ? x : y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M >> R >> P;
for (int i = 1; i <= N; ++i) {
cin >> val[i];
}
for (int i = 1; i < N; ++i) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
// 第一次DFS预处理
dfs1(R, 0);
current_pos = 0;
// 第二次DFS进行重链剖分
dfs2(R, 0, R);
// 构建线段树
vector<int> datas(N + 1);
for (int i = 1; i <= N; ++i) {
datas[pos[i]] = val[i] % P;
}
tree.resize(4 * (N + 1));
build(datas, tree, 1, 1, N);
// 处理操作
while (M--) {
int cmd;
cin >> cmd;
if (cmd == 1) { // 路径更新
int x, y, z;
cin >> x >> y >> z;
pathUpdate(x, y, z);
} else if (cmd == 2) { // 路径查询
int x, y;
cin >> x >> y;
cout << pathQuery(x, y) << '\n';
} else if (cmd == 3) { // 子树更新
int x, z;
cin >> x >> z;
subtreeUpdate(x, z);
} else if (cmd == 4) { // 子树查询
int x;
cin >> x;
cout << subtreeQuery(x) << '\n';
}
}
return 0;
}const int MAXN = 1e5 + 5; // 最大节点数
int N, M, R; // 节点数、操作数、根节点
vector<int> adj[MAXN]; // 邻接表存储树结构
int val[MAXN]; // 节点初始权值
// 树链剖分相关变量
int parent[MAXN]; // 父节点
int depth[MAXN]; // 节点深度
int sz[MAXN]; // 子树大小
int heavy[MAXN]; // 重儿子
int pos[MAXN]; // 节点在线段树中的位置
int top[MAXN]; // 所在重链的顶部节点
int current_pos; // 当前DFS序位置
// 线段树节点结构
struct node {
int data; // 节点值
int lazy; // 懒标记
node() : data(0), lazy(0) {}
};
vector<node> tree; // 线段树
// 构建线段树
void build(const vector<int>& datas, vector<node>& tree, int rt, int left, int right) {
if (left == right) {
tree[rt].data = datas[left];
return;
}
int mid = left + (right - left) / 2;
build(datas, tree, 2 * rt, left, mid);
build(datas, tree, 2 * rt + 1, mid + 1, right);
tree[rt].data = tree[2 * rt].data + tree[2 * rt + 1].data;
}
// 下传懒标记
void pushDown(vector<node>& tree, int rt, int len) {
if (tree[rt].lazy != 0) {
tree[rt * 2].data = tree[rt * 2].data + tree[rt].lazy * (len - len / 2);
tree[rt * 2].lazy = tree[rt * 2].lazy + tree[rt].lazy;
tree[rt * 2 + 1].data = tree[rt * 2 + 1].data + tree[rt].lazy * (len / 2);
tree[rt * 2 + 1].lazy = tree[rt * 2 + 1].lazy + tree[rt].lazy;
tree[rt].lazy = 0;
}
}
// 线段树区间查询
int query(vector<node>& tree, int rt, int left, int right, int ql, int qr) {
if (ql > right || qr < left) {
return 0;
}
if (ql <= left && qr >= right) {
return tree[rt].data;
}
pushDown(tree, rt, right - left + 1);
int mid = left + (right - left) / 2;
int leftsum = query(tree, 2 * rt, left, mid, ql, qr);
int rightsum = query(tree, 2 * rt + 1, mid + 1, right, ql, qr);
return leftsum + rightsum;
}
// 线段树区间更新
void updateRange(vector<node>& tree, int rt, int left, int right, int ul, int ur, int value) {
if (ul > right || ur < left) return;
if (ul <= left && ur >= right) {
tree[rt].data = tree[rt].data + value * (right - left + 1);
tree[rt].lazy = tree[rt].lazy + value;
return;
}
pushDown(tree, rt, right - left + 1);
int mid = left + (right - left) / 2;
updateRange(tree, 2 * rt, left, mid, ul, ur, value);
updateRange(tree, 2 * rt + 1, mid + 1, right, ul, ur, value);
tree[rt].data = tree[2 * rt].data + tree[2 * rt + 1].data;
}
// 第一次DFS:计算父节点、深度、子树大小和重儿子
void dfs1(int u, int p) {
parent[u] = p;
depth[u] = depth[p] + 1;
sz[u] = 1;
heavy[u] = 0;
for (int v : adj[u]) {
if (v != p) {
dfs1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[heavy[u]]) {
heavy[u] = v;
}
}
}
}
// 第二次DFS:进行重链剖分,计算DFS序和重链顶部
void dfs2(int u, int p, int chain_top) {
pos[u] = ++current_pos;
top[u] = chain_top;
if (heavy[u]) {
dfs2(heavy[u], u, chain_top);
}
for (int v : adj[u]) {
if (v != p && v != heavy[u]) {
dfs2(v, u, v);
}
}
}
// 路径更新:将x到y路径上的节点值都加上z
void pathUpdate(int x, int y, int z) {
while (top[x] != top[y]) {
if (depth[top[x]] > depth[top[y]]) {
swap(x, y);
}
updateRange(tree, 1, 1, N, pos[top[y]], pos[y], z);
y = parent[top[y]];
}
if (depth[x] > depth[y]) {
swap(x, y);
}
updateRange(tree, 1, 1, N, pos[x], pos[y], z);
}
// 路径查询:查询x到y路径上的节点值之和
int pathQuery(int x, int y) {
int res = 0;
while (top[x] != top[y]) {
if (depth[top[x]] > depth[top[y]]) {
swap(x, y);
}
res = res + query(tree, 1, 1, N, pos[top[y]], pos[y]);
y = parent[top[y]];
}
if (depth[x] > depth[y]) {
swap(x, y);
}
res = res + query(tree, 1, 1, N, pos[x], pos[y]);
return res;
}
// 子树更新:将以x为根的子树所有节点值加上z
void subtreeUpdate(int x, int z) {
int l = pos[x];
int r = pos[x] + sz[x] - 1;
updateRange(tree, 1, 1, N, l, r, z);
}
// 子树查询:查询以x为根的子树所有节点值之和
int subtreeQuery(int x) {
int l = pos[x];
int r = pos[x] + sz[x] - 1;
return query(tree, 1, 1, N, l, r);
}
// 求两个节点的最近公共祖先(LCA)
int lca(int x, int y) {
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]]) {
swap(x, y);
}
x = parent[top[x]];
}
return depth[x] < depth[y] ? x : y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M >> R;
for (int i = 1; i <= N; ++i) {
cin >> val[i];
}
for (int i = 1; i < N; ++i) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
// 第一次DFS预处理
dfs1(R, 0);
current_pos = 0;
// 第二次DFS进行重链剖分
dfs2(R, 0, R);
// 构建线段树
vector<int> datas(N + 1);
for (int i = 1; i <= N; ++i) {
datas[pos[i]] = val[i];
}
tree.resize(4 * (N + 1));
build(datas, tree, 1, 1, N);
// 处理操作
while (M--) {
int cmd;
cin >> cmd;
if (cmd == 1) { // 路径更新
int x, y, z;
cin >> x >> y >> z;
pathUpdate(x, y, z);
} else if (cmd == 2) { // 路径查询
int x, y;
cin >> x >> y;
cout << pathQuery(x, y) << '\n';
} else if (cmd == 3) { // 子树更新
int x, z;
cin >> x >> z;
subtreeUpdate(x, z);
} else if (cmd == 4) { // 子树查询
int x;
cin >> x;
cout << subtreeQuery(x) << '\n';
}
}
return 0;
}#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));
}
struct KruskalReconstructionTree {
int n; // 原图节点数
int tot; // 重构树总节点数
vector<vector<int>> g; // 树邻接表
vector<int> val; // 节点权值 (原节点 -1)
vector<int> parent; // 父节点
vector<int> dsu; // 并查集
static const int LOG = 20; // 倍增 LCA 参数
vector<int> depth;
vector<vector<int>> up;
KruskalReconstructionTree(int n_) : n(n_) {
tot = n;
g.resize(2 * n);
val.resize(2 * n);
parent.assign(2 * n, -1);
dsu.resize(2 * n);
iota(dsu.begin(), dsu.end(), 0);
for (int i = 0; i < n; i++) val[i] = -1;
depth.resize(2 * n);
}
int find(int x) {
while (dsu[x] != x) dsu[x] = dsu[dsu[x]], x = dsu[x];
return x;
}
// 构建重构树。edges: {u,v,w}
void build(vector<tuple<int, int, int>> edges, bool sorted = false) {
if (!sorted) {
sort(edges.begin(), edges.end(),
[](const auto &a, const auto &b) {
return get<2>(a) > get<2>(b); // 最大瓶颈路
});
}
for (auto &[u, v, w] : edges) {
int ru = find(u), rv = find(v);
if (ru == rv) continue;
int node = tot++;
val[node] = w;
g[node].push_back(ru);
g[node].push_back(rv);
parent[ru] = parent[rv] = node;
dsu[ru] = dsu[rv] = node;
dsu[node] = node;
if (tot >= (int)g.size()) {
g.resize(tot + 5);
val.resize(tot + 5);
parent.resize(tot + 5);
depth.resize(tot + 5);
}
}
g.resize(tot);
val.resize(tot);
parent.resize(tot);
// 建立倍增表
initLCA();
}
void initLCA() {
depth.assign(tot, 0);
up.assign(tot, vector<int>(LOG, -1));
for (int i = 0; i < tot; i++)
if (parent[i] == -1) dfs(i, -1);
}
void dfs(int u, int p) {
up[u][0] = p;
for (int j = 1; j < LOG; j++) {
if (up[u][j - 1] != -1)
up[u][j] = up[up[u][j - 1]][j - 1];
else
up[u][j] = -1;
}
for (int v : g[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
// 查询 u, v 的 LCA
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int j = 0; j < LOG; j++) {
if (diff >> j & 1) u = up[u][j];
}
if (u == v) return u;
for (int j = LOG - 1; j >= 0; j--) {
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
// 查询原图 u->v 瓶颈路(最小边权的最大值)
int queryMaxEdgeMin(int u, int v) {
int w = lca(u, v);
if (w == -1) return -1;
return val[w];
}
// 从 s 出发,仅走边权 ≤ lim 的边能到达的所有节点
vector<int> queryReachable(int s, int lim) {
int u = s;
for (int j = LOG - 1; j >= 0; j--)
if (up[u][j] != -1 && val[up[u][j]] <= lim)
u = up[u][j];
vector<int> res;
collectLeaves(u, -1, res);
return res;
}
// 从 s 出发,仅走边权 ≥ lim 的边能到达的所有节点(需降序构建)
vector<int> queryReachableMin(int s, int lim) {
int u = s;
for (int j = LOG - 1; j >= 0; j--)
if (up[u][j] != -1 && val[up[u][j]] >= lim)
u = up[u][j];
vector<int> res;
collectLeaves(u, -1, res);
return res;
}
// 收集子树中所有原图节点
void collectLeaves(int u, int p, vector<int> &out) {
if (u < n) { out.push_back(u); return; }
for (int v : g[u]) if (v != p) collectLeaves(v, u, out);
}
};#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3,M=153,P=10007;
int n,m,x,y,o,K,jc[M],fto[M],head[N],S[M][M],f[N][M],g[N][M];
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 dp=0;x=0;char c=getchar();
while(c<'0'||c>'9')dp|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=dp?-x:x;
}
inline void dfs1(Re x,Re fa){
f[x][0]=1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs1(to,x),(f[x][0]+=f[to][0])%=P;
for(Re j=1;j<=K;++j)(f[x][j]+=(f[to][j]+f[to][j-1])%P)%=P;
}
}
inline void dfs2(Re x,Re fa){
if(fa){
fto[0]=(g[fa][0]+f[fa][0]-f[x][0]+P)%P;
for(Re j=1;j<=K;++j)fto[j]=(g[fa][j]+f[fa][j]-(f[x][j]+f[x][j-1])%P+P)%P;
g[x][0]=fto[0];
for(Re j=1;j<=K;++j)g[x][j]=(fto[j]+fto[j-1])%P;
}
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dfs2(to,x);
}
inline void Stirling(Re N){
for(Re i=0;i<=N;++i)S[i][i]=1;
for(Re i=1;i<=N;++i)
for(Re j=1;j<i;++j)
S[j][i]=(S[j-1][i-1]+j*S[j][i-1]%P)%P;
}
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);
dfs1(1,0),dfs2(1,0),Stirling(K),jc[0]=1;
for(Re i=1;i<=K;++i)jc[i]=jc[i-1]*i%P;
for(Re i=1;i<=n;++i){
Re ans=0;
for(Re j=0;j<=K;++j)
(ans+=S[j][K]*jc[j]%P*(f[i][j]+g[i][j])%P)%=P;
printf("%d\n",ans);
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const LL N=1e5+3,inf=1e18;
int n,m,x,y,z,o,A[N],S[N],dis[N],size[N],head[N];LL ans=inf,f[N],g[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;
}
inline void dfs1(Re x,Re fa){
size[x]=1,S[x]=A[x];
for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)
dis[to]=a[i].w,dfs1(to,x),S[x]+=S[to],size[x]+=size[to],f[x]+=f[to]+(LL)S[to]*a[i].w;
}
inline void dfs2(Re x,Re fa){
if(fa)g[x]=g[fa]+f[fa]-f[x]-(LL)S[x]*dis[x]+(LL)(S[1]-S[x])*dis[x];
for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)dfs2(to,x);
ans=min(ans,f[x]+g[x]);
}
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),in(z),add(x,y,z),add(y,x,z);
dfs1(1,0),dfs2(1,0),printf("%lld\n",ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
int head[6010],a,b,t,i,j,n,f[6010][2],pan[6010];
struct QAQ{int next,to;}Q[6010];
inline void add(int x,int y){Q[++t].to=y,Q[t].next=head[x],head[x]=t;}
inline void dfs(int w){
for(R k=head[w];k;k=Q[k].next){
int to=Q[k].to;
dfs(to);
f[w][0]+=max(f[to][0],f[to][1]);
f[w][1]+=f[to][0];
}
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&f[i][1]);
for(i=1;i<n;i++)scanf("%d%d",&a,&b),pan[a]++,add(b,a);
for(i=1;i<=n;i++)
if(!pan[i]){
dfs(i);
printf("%d\n",max(f[i][0],f[i][1]));
return 0;
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
struct QAQ{int to,next;}a[1505];
int m,pan[1505],n,t,w[1505],dp[1505][3],head[1505];
inline void add(int x,int y){a[++t].to=y,a[t].next=head[x],head[x]=t;}
//dp[i][0] 以及各种情况的具体转移方程和初始状态
inline void dfs(int x){
R i,to,dd=0xfffffff;
dp[x][1]=w[x];dp[x][2]=0;dp[x][0]=0;
for(i=head[x];i;i=a[i].next){
dfs(to=a[i].to);
dd=min(dd,dp[to][1]-min(dp[to][0],dp[to][1]));
dp[x][0]+=min(dp[to][0],dp[to][1]);
dp[x][1]+=min(dp[to][1],dp[to][2]);
dp[x][2]+=min(dp[to][0],dp[to][1]);
}
dp[x][0]+=dd;
}
int main(){
memset(dp,127,sizeof(dp));
scanf("%d",&n);
R i,j,a,k,r;
for(i=1;i<=n;i++){
scanf("%d%d%d",&a,&k,&m);w[a]=k;
for(j=1;j<=m;j++)scanf("%d",&r),pan[r]=1,add(a,r);
}
for(i=1;i<=n;i++)
if(!pan[i]){
dfs(i);
printf("%d",min(dp[i][1],dp[i][0]));
return 0;
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5003,P=998244353;
int n,m,o,x,y,f[N],g[N],A[N],jc[N],head[N];char s[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 int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
int sz1[N],sz0[N],lim[N],dp[N][N],tmp[N];
inline void dfs0(Re x,Re fa){
sz0[x]=(!A[x]),sz1[x]=A[x];
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dfs0(to,x),sz1[x]+=sz1[to],sz0[x]+=sz0[to];
// lim[x]=min(sz1[x],size[x]-sz1[x]);
}
inline void dfs(Re x,Re fa){
dp[x][0]=1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x);
for(Re j=0;j<=lim[x]+lim[to];++j)tmp[j]=0;
for(Re j=lim[x];j>=0;--j)
for(Re k=lim[to];k>=0;--k)
(tmp[j+k]+=(LL)dp[x][j]*dp[to][k]%P)%=P;
lim[x]+=lim[to];
for(Re j=0;j<=lim[x];++j)dp[x][j]=tmp[j];
}
++lim[x];
if(A[x])for(Re j=min(lim[x],sz0[x]);j>=1;--j)
(dp[x][j]+=(LL)dp[x][j-1]*(sz0[x]-(j-1))%P)%=P;
else for(Re j=min(lim[x],sz1[x]);j>=1;--j)
(dp[x][j]+=(LL)dp[x][j-1]*(sz1[x]-(j-1))%P)%=P;
while(!dp[x][lim[x]])--lim[x];
}
inline int C(Re m,Re n){return (LL)jc[n]*inv(jc[m])%P*inv(jc[n-m])%P;}
int main(){
// freopen("match.in","r",stdin);
// freopen("match.out","w",stdout);
in(n),scanf("%s",s+1),m=n-1,jc[0]=1;
for(Re i=1;i<=n;++i)A[i]=s[i]-'0',jc[i]=(LL)jc[i-1]*i%P;
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs0(1,0),dfs(1,0);
// for(Re i=1;i<=n;++i)printf("lim[%d]=%d\n",i,lim[i]);
// for(Re i=0;i<=n/2;++i)printf("dp[%d]=%d\n",i,dp[1][i]);
// for(Re j=0;j<=lim[1];++j)printf("%d ",dp[1][j]);
for(Re j=0;j<=lim[1];++j)g[j]=(LL)dp[1][j]*jc[n/2-j]%P;
for(Re i=lim[1];i>=0;--i){
f[i]=g[i];
for(Re j=i+1;j<=lim[1];++j)f[i]=(f[i]-(LL)C(i,j)*f[j]%P+P)%P;
}
for(Re i=0;i<=n/2;++i)printf("%d\n",f[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2003;
int n,m,x,y,z,o,K,size[N],head[N];LL tmp[N],dp[N][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;
}
inline void dfs(Re x,Re fa){
size[x]=1,dp[x][0]=dp[x][1]=0;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x);
for(Re j=0;j<=size[x]+size[to];++j)tmp[j]=dp[0][0];
for(Re j=size[x];j>=0;--j)
if(dp[x][j]>=0)for(Re k=size[to];k>=0;--k)
if(dp[to][k]>=0)
tmp[j+k]=max(tmp[j+k],dp[x][j]+dp[to][k]+
(LL)a[i].w*((LL)k*(K-k)+(LL)(size[to]-k)*(n-size[to]-(K-k)))
);
size[x]+=size[to];
for(Re j=0;j<=size[x];++j)dp[x][j]=tmp[j];
}
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(K),m=n-1;
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
memset(dp,-20,sizeof(dp));
dfs(1,0),printf("%lld\n",dp[1][K]);
}