思路

因为这个题目的 $n$ 只有 $2\times 10^5$ 而且是由乃的题目，直接一眼分块。

因为这个题目的空间限制太毒瘤了，所以我们并不能直接开一个大小为 $n\cdot \sqrt{n}$ 的数组，而是需要将询问离线，每一次处理一个块对答案的贡献，于是空间就压缩到了 $\sqrt{n}$。

对于每一块一共有四种操作：散块单独修改或查询和整块修改或查询。

1.整块修改

一个区间内可能会更新答案的点 $k$ 都满足性质：对于 $i\in[l,r]$ 且 $i\ne k$ 均有 $\operatorname{lca}(i,k)\ne i$。这个性质很好理解，因为所有的边权均为正数。如果 $\operatorname{lca}(i,k)=i$ 那么 $dep_k=dep_i+dis(i,k)$ 其中 $dis(i,k)$ 为两点之间的距离，显然这个 $dis$ 是大于等于 $0$ 的，所以纵使 $dep_k$ 先更新了答案，最终答案也会被 $dep_i$ 再次更新。

如果在序列的最初判断一个块内是否存在 $\operatorname{lca}(i,k)=i$ 的时间复杂度是 $O(n\log n)$ 的无法接受，所以我们可以考虑优化。我们在访问这个块的时候先将访问过的点进行标记，接着将所有的点全部放入集合中。如果在后面的操作中访问到了已经标记过的节点，那么就不把这个点加入集合，因为显然有一个节点是他的祖先。因为即使是在最差的情况下所有的节点也都只会进入集合一次，所以处理一块的时间复杂度为 $O(n)$，因为一共有 $\sqrt{n}$ 块所以总共的时间复杂度为 $O(n\cdot\sqrt{n})$ 可以接受。

但是可能出现一些节点原本已经是一些节点了后代了，但是因为散块修改导致他有超过了他的祖先。所以在操作时，虽然我们并不需要真正让所有的节点向上跳，但是我们需要记录下所有的节点一起向上移动的次数，并打上一个懒惰标记，在散块修改时处理掉。

2. 散块修改

因为散块修改在所有 $m$ 次询问时不会超过 $2\cdot m$ 次，所以不妨可以暴力一点直接模拟题目所给的操作。但是因为在整块修改时我们打了对整块的修改打上懒惰标记，所以需要将每一个点全部赋值为自己的懒惰标记数量级祖先。在这其实很好实现，直接使用重链剖分向上跳就可以了。因为在区间修改时，在整块修改的时候统计的祖先的标记已经被更新了，所以还需要更新有意义的节点。所有 $m$ 次操作整体的时间复杂度为 $O(m\cdot\log n\cdot\sqrt{n})$。

3.整块查询

对于整块查询，我们可以直接遍历有意义的集合更新答案。

4. 散块查询

我们可以将所有的懒惰标记全部更新掉，接着只是遍历这 $\sqrt{n}$ 个数直接暴力更新答案。

AC Code

引用一句话：“自从我写了由乃的题目，我就从来都没有注意过我的代码长度了。”

#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
using ll=long long; 
const int N=2e5+5,M=450;
int n,m,q,rt,siz[N],dep[N],ff[N],son[N],mp[N],dfn[N],cnt,top[N];
ll xwd[N],dis[N];
struct node{int x,val;};
vector<node> v[N];
void dfs1(int x,int fa){
	dep[x]=dep[fa]+1;
	ff[x]=fa;
	siz[x]=1;
	for(node i:v[x]){
		if(i.x==fa){
			continue;
		}
		dis[i.x]=dis[x]+i.val;
		dfs1(i.x,x);
		siz[x]+=siz[i.x];
		if(siz[son[x]]<siz[i.x]){
			son[x]=i.x;
		}
	}
}
void dfs2(int x,int fa){
	if(son[x]){
		dfn[son[x]]=++cnt;
		top[son[x]]=top[x];
		mp[cnt]=son[x];
		dfs2(son[x],x);
	}
	for(node i:v[x]){
		if(i.x==fa||i.x==son[x]){
			continue;
		}
		dfn[i.x]=++cnt;
		top[i.x]=i.x;
		mp[cnt]=i.x;
		dfs2(i.x,x);
	}
}
int a[N];
struct mdf{int op,l,r;}ask[N];
int l[M],r[M];
void pre(){
	m=sqrt(n);
	for(int i=1;i<=m;i++){
		l[i]=r[i-1]+1;
		r[i]=i*m;
	}
	if(r[m]<n){
		m++;
		l[m]=r[m-1]+1;
		r[m]=n;
	}
}
bool vis[N];
void pushdown(int &x,int cnt){
	if(dep[x]<=cnt){
		x=rt;
		return; 
	}
	while(dep[x]-dep[top[x]]+1<=cnt){
		cnt-=dep[x]-dep[top[x]]+1;
		x=ff[top[x]];
	}
	x=mp[dfn[x]-cnt];
}
void solve(int l,int r){
	vector<int> nodes,g;
	ll ans=0x7f7f7f7f7f7f7f7f;
	int lazy=0;
	memset(vis,0,sizeof(vis));
	for(int i=l;i<=r;i++){
		ans=min(ans,dis[a[i]]);
		nodes.push_back(a[i]);
		vis[a[i]]=1;
	}
	for(int i=1;i<=q;i++){
		if(ask[i].l>r||ask[i].r<l){
			continue;
		}
		if(ask[i].op==1){
			if(ask[i].l<=l&&r<=ask[i].r){
				g=nodes;
				lazy++;
				nodes.clear();
				for(int j=0;j<(int)g.size();j++){
					g[j]=ff[g[j]];
					ans=min(ans,dis[g[j]]);
					if(!vis[g[j]]){
						vis[g[j]]=1;
						nodes.push_back(g[j]);
					}
				}
				g.clear();
			}
			else{
				for(int j=l;j<=r;j++){
					pushdown(a[j],lazy);
				}
				lazy=0;
				int ll=max(l,ask[i].l),rr=min(r,ask[i].r);
				for(int j=ll;j<=rr;j++){
					a[j]=ff[a[j]];
				}
				nodes.clear();
				for(int j=l;j<=r;j++){
					ans=min(ans,dis[a[j]]);
					vis[a[j]]=1;
					nodes.push_back(a[j]);
				}
			}
		}
		else{
			if(ask[i].l<=l&&r<=ask[i].r){
				xwd[i]=min(xwd[i],ans);
			}
			else{
				for(int j=l;j<=r;j++){
					pushdown(a[j],lazy);
					ans=min(ans,dis[a[j]]);
					vis[a[j]]=1;
				}
				lazy=0;
				int ll=max(l,ask[i].l),rr=min(r,ask[i].r);
				for(int j=ll;j<=rr;j++){
					xwd[i]=min(xwd[i],dis[a[j]]);
				}
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>q>>rt;
	for(int i=1,a,b,val;i<n;i++){
		cin>>a>>b>>val;
		v[a].push_back({b,val});
		v[b].push_back({a,val});
	}
	dfs1(rt,rt);
	dfn[rt]=++cnt;
	top[rt]=rt;
	mp[cnt]=rt;
	ff[rt]=rt;
	dfs2(rt,rt);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=q;i++){
		cin>>ask[i].op>>ask[i].l>>ask[i].r;
	}
	pre();
	memset(xwd,0x7f,sizeof(xwd));
	for(int i=1;i<=m;i++){
		solve(l[i],r[i]);
	}
	for(int i=1;i<=q;i++){
		if(ask[i].op==2){
			cout<<xwd[i]<<'\n';
		}
	}
	return 0;
}