#include #include #include #include #include #include #include #include #include #include #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template void chmin(T &a,const T &b){if(a>b) a=b;} template void chmax(T &a,const T &b){if(a> g; int root; vector parent[MAX_LOG_V]; vector depth; LowestCommonAncestor(){} LowestCommonAncestor(int V,int root_):g(V),depth(V){ root=root_; for(int i=0;idepth[v]) swap(u,v); for(int k=0;k>k&1){ v=parent[k][v]; } } if(u==v) return u; for(int k=MAX_LOG_V-1;k>=0;k--){ if(parent[k][u]!=parent[k][v]){ u=parent[k][u]; v=parent[k][v]; } } return parent[0][u]; } }; struct Centroid{ vector> g; vector sz,dead; Centroid(){} Centroid(int V):sz(V,1),dead(V,0),g(V){} void initialize(int V){ sz.resize(V,1); dead.resize(V,0); g.resize(V); } void add_edge(int u,int v){ g[u].push_back(v); g[v].push_back(u); } int szdfs(int now,int par){ sz[now]=1; for(auto nex:g[now]){ if(nex==par||dead[nex]) continue; sz[now]+=szdfs(nex,now); } return sz[now]; } void findCentroid(int now,int par,int V,vector &cens){ bool ok=true; for(auto nex:g[now]){ if(nex==par||dead[nex]) continue; findCentroid(nex,now,V,cens); if(sz[nex]>V/2) ok=false; } if(V-sz[now]>V/2) ok=false; if(ok) cens.push_back(now); } vector build(int root){ vector cens; szdfs(root,-1); findCentroid(root,-1,sz[root],cens); return cens; } void kill(int now){ dead[now]=1; } bool alive(int now){ return dead[now]==0; } }; int parent[100010]; ll sum[100010],num[100010]; map,ll> mp; Centroid cent; LowestCommonAncestor lca; void decompose(int now,int par){ vector cs=cent.build(now); int C=cs[0]; cent.kill(C); parent[C]=par; for(auto nex:cent.g[C]){ if(cent.alive(nex)) decompose(nex,C); } } void paint(int target,bool f){ int v=target; while(v!=-1){ int u=lca.query(target,v); int cost=lca.depth[target]+lca.depth[v]-2*lca.depth[u]; if(parent[v]!=-1){ int t=lca.query(target,parent[v]); int tmp=lca.depth[target]+lca.depth[parent[v]]-2*lca.depth[t]; if(f){ mp[mkp(parent[v],v)]+=tmp; }else{ mp[mkp(parent[v],v)]-=tmp; } } if(f){ sum[v]+=cost; num[v]++; }else{ sum[v]-=cost; num[v]--; } v=parent[v]; } } ll query(int target){ ll res=0; int v=target; while(v!=-1){ int u=lca.query(target,v); int cost=lca.depth[target]+lca.depth[v]-2*lca.depth[u]; res+=sum[v]+cost*num[v]; if(parent[v]!=-1){ int t=lca.query(target,parent[v]); int tmp=lca.depth[target]+lca.depth[parent[v]]-2*lca.depth[t]; res-=(mp[mkp(parent[v],v)]+(tmp)*num[v]); } v=parent[v]; } return res; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,K,Q; cin>>N>>K>>Q; vector C(K); rep(i,K) cin>>C[i]; rep(i,K) C[i]--; vector U(N-1),V(N-1); rep(i,N-1) cin>>U[i]>>V[i]; rep(i,N-1){ U[i]--;V[i]--; } cent.initialize(N); rep(i,N-1) cent.add_edge(U[i],V[i]); lca.initialize(N,0); rep(i,N-1) lca.add_edge(U[i],V[i]); lca.build(N); decompose(0,-1); rep(i,K) paint(C[i],true); for(int q=0;q>t; if(t==1){ int p,d; cin>>p>>d; p--;d--; paint(C[p],false); C[p]=d; paint(C[p],true); }else{ int e; cin>>e; e--; cout<