这题如果对于每个块维护每个点是否出现过，空间复杂度是 $O(n\sqrt n)$ 的，开不下

而我又不想离线，于是就对每个块用 $set$ 维护 $dfs$ 序上的区间来去重

然后发现大数据能过，小数据 $WA$ 了：记录

是我做法假了还是我哪里写挂了

using namespace std;
int n,m,rt;
int ver[400005],ne[400005],head[200005],cnt;
long long val[400005];
inline void link(int x,int y,long long v){
	ver[++cnt]=y;
	ne[cnt]=head[x];
	head[x]=cnt;val[cnt]=v;
}
long long dep[200005];
int fa[23][200005],dfn[200005],tot,siz[200005];
void dfs(int x,int fi){
	fa[0][x]=fi;dfn[x]=++tot;siz[x]=1;
	for(int i=1;i<23;i++)fa[i][x]=fa[i-1][fa[i-1][x]];
	for(int i=head[x];i;i=ne[i]){
		int u=ver[i];
		if(u==fi)continue;
		dep[u]=dep[x]+val[i];
		dfs(u,x);siz[x]+=siz[u];
	}
}
int sqr[200005],a[200005],le[505],ri[505],s=500;
struct node{
	int l,r;
	node(int _x){
		l=dfn[_x];r=dfn[_x]+siz[_x]-1;
	}
	node(int _l,int _r){
		l=_l;r=_r;
	}
	inline bool operator <(const node &b)const{
		if(r!=b.r)return r<b.r;
		return l>b.l;
	}
};
set<node> vis[505];
long long ans[505];
vector<int> vec[505];
inline void build(int x){
	vec[x].clear();vis[x].clear();
	for(int i=le[x];i<=ri[x];i++){
		auto it=vis[x].lower_bound(node(a[i]));
		if(it!=vis[x].end()&&it->l<=dfn[a[i]])continue;
		auto r=vis[x].insert(node(a[i])).first;auto l=vis[x].lower_bound(node(dfn[a[i]],dfn[a[i]]));
		while(l!=r)l=vis[x].erase(l);
	}
	for(int i=le[x];i<=ri[x];i++)ans[x]=min(ans[x],dep[a[i]]);
}
int tag[505],mp[1<<20];
inline void jump(int x){
	vector<int> tmp;tag[x]++;
	for(auto u:vec[x]){
		int t=fa[0][u];vis[x].erase(node(u));
		auto it=vis[x].lower_bound(node(t));
		if(it!=vis[x].end()&&it->l<=dfn[t])continue;
		auto r=vis[x].insert(node(t)).first;auto l=vis[x].lower_bound(node(dfn[t],dfn[t]));
		while(l!=r)l=vis[x].erase(l);
		ans[x]=min(ans[x],dep[t]);tmp.push_back(t);
	}swap(vec[x],tmp);
}
inline int top(int x,int y){
	while(y){
		int len=mp[y&-y];x=fa[len][x];
		y&=(y-1);
	}return x;
}
inline void update(int l,int r){
	for(int i=le[sqr[l]];i<=ri[sqr[l]];i++)a[i]=top(a[i],tag[sqr[i]]);
	tag[sqr[l]]=0;
	for(int i=l;i<=r&&i<=ri[sqr[l]];i++)a[i]=fa[0][a[i]];
	build(sqr[l]);
	if(sqr[l]==sqr[r])return ;
	for(int i=sqr[l]+1;i<sqr[r];i++)jump(i);
	for(int i=le[sqr[r]];i<=ri[sqr[r]];i++)a[i]=top(a[i],tag[sqr[i]]);
	tag[sqr[r]]=0;
	for(int i=le[sqr[r]];i<=r;i++)a[i]=fa[0][a[i]];
	build(sqr[r]);
}
inline long long query(int l,int r){
	long long res=1e14;
	for(int i=l;i<=r&&i<=ri[sqr[l]];i++)res=min(res,dep[top(a[i],tag[sqr[i]])]);
	if(sqr[l]==sqr[r])return res;
	for(int i=sqr[l]+1;i<sqr[r];i++)res=min(res,ans[i]);
	for(int i=le[sqr[r]];i<=r;i++)res=min(res,dep[top(a[i],tag[sqr[i]])]);
	return res;
}
int main(){
	scanf("%d%d%d",&n,&m,&rt);
	for(int i=1;i<n;i++){
		int x,y;long long v;
		scanf("%d%d%lld",&x,&y,&v);
		link(x,y,v);link(y,x,v);
	}
	dfs(rt,rt);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=0;i<20;i++)mp[1<<i]=i;
	for(int i=1;i<=n;i++)sqr[i]=i/s+1;
	for(int i=1;i<=n;i++)ri[sqr[i]]=i;
	for(int i=n;i>=0;i--)le[sqr[i]]=i;
	for(int i=1;i<=sqr[n];i++)ans[i]=1e14;
	for(int i=1;i<=sqr[n];i++)build(i);
	while(m--){
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)update(l,r);
		else printf("%lld\n",query(l,r));
	}

	return 0;
}