#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]; ll all[100010]; map,ll> mp; Centroid cent; LowestCommonAncestor lca; int slime[100010]; pair dfs(int now,int par){ int res=0,ns=slime[now]; for(auto nex:cent.g[now]){ if(cent.alive(nex)==false) continue; if(nex==par) continue; auto f=dfs(nex,now); res+=f.first+f.second; ns+=f.second; } return mkp(res,ns); } void decompose(int now,int par){ vector cs=cent.build(now); int C=cs[0]; cent.kill(C); parent[C]=par; /*auto val=dfs(C,-1); sum[C]=val.first; num[C]=val.second; if(par!=-1){ int u=lca.query(C,par); int cost=lca.depth[C]+lca.depth[par]-2*lca.depth[u]; all[par]+=sum[C]+num[C]*cost; mp[mkp(par,now)]=sum[C]+num[C]*cost; }*/ for(auto nex:cent.g[C]){ if(cent.alive(nex)) decompose(nex,C); } } void paint(int target,bool f){ int v=target; int d=0; 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(v,parent[v]); int tmp=lca.depth[v]+lca.depth[parent[v]]-2*lca.depth[t]; if(f){ all[parent[v]]+=cost+tmp; mp[mkp(parent[v],v)]+=cost+tmp; }else{ all[parent[v]]-=cost+tmp; mp[mkp(parent[v],v)]-=cost+tmp; } } if(f){ sum[v]+=cost; num[v]++; }else{ sum[v]-=cost; num[v]--; } v=parent[v]; } } ll query(int target){ ll res=sum[target]; int v=target; int d=0; int child=-1; while(v!=-1){ int u=lca.query(target,v); int cost=lca.depth[target]+lca.depth[v]-2*lca.depth[u]; if(child!=-1){ int t=lca.query(v,child); int tmp=lca.depth[v]+lca.depth[child]-2*lca.depth[t]; d+=tmp; } if(v!=target) res+=all[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]); } child=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); rep(i,K) slime[C[i]]++; 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<