题面
题解
区间置 fa 问题。
根据题目 “时代的眼泪” 的提示， 考虑对序列 \(a\) 分块，散点往上跳我们暴力更新，下面我们只考虑整块往上跳：
实际上，若块中有一点 \(x\)，往上跳到 \(y\)，但如果 \(y\) 已经被同一块内的访问过了，那么证明有另一点在 \(x\) 的更高处，此时 \(x\) 就可以删掉了。所以我们使用一个数据结构来维护块中还有贡献的 \(x\)。这样每个块只会访问整棵树一次，时间复杂度 \(O((n+q)\sqrt{n})\)。
需要会长链剖分 \(O(n\log n)-O(1)\) 求 \(k\) 级祖先，否则会带上 \(\log\)。
代码如下：（我被极度卡常了）
#include<bits/stdc++.h>
#define LN 18
#define SN 510
#define N 200010
#define ll long long
#define re register
#define LNF 0x7fffffffffffffff
using namespace std;
char ibuf[1<<25],*ih=ibuf,obuf[1<<25],*oh=obuf;
inline int read(){
int x;
for(;!isdigit(*ih);++ih);
for(x=0;isdigit(*ih);x=x*10+*ih++-48);
return x;
}
inline void out(ll x){
if(!x){*oh++='0';return;}
static int buf[30];int xb=0;
for(;x;x/=10)buf[++xb]=x%10;
for(;xb;)*oh++=buf[xb--]|48;
}
int pow2[N],highbit[N];
int n,m,rt,a[N];
int cnt,head[N],nxt[N<<1],to[N<<1],w[N<<1];
int fa[N][LN];
int son[N],maxd[N],top[N];
ll dis[N],minn[SN];
int B,len,bl[N],bll[SN],blr[SN];
int tag[SN];
bool vis[SN][N];
int inq[N];
int Q[SN][SN],tail[SN];
inline void push(const int b,const int x)
{
Q[b][++tail[b]]=x;
inq[x]=tail[b];
}
inline void del(const int b,const int x)
{
if(x==tail[b])
{
inq[Q[b][x]]=0;
tail[b]--;
return;
}
inq[Q[b][x]]=0,inq[Q[b][tail[b]]]=x;
swap(Q[b][x],Q[b][tail[b]]);
tail[b]--;
}
vector<int>up[N],down[N];
void adde(int u,int v,int wi)
{
to[++cnt]=v;
w[cnt]=wi;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int u)
{
for(re int i=1;i<=17;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(re int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa[u][0]) continue;
fa[v][0]=u;
dis[v]=dis[u]+w[i];
dfs(v);
maxd[u]=max(maxd[u],maxd[v]+1);
if(!son[u]||maxd[v]>maxd[son[u]]) son[u]=v;
}
}
void dfs1(int u,int tp)
{
top[u]=tp;
if(son[u]) dfs1(son[u],tp);
for(re int i=head[u];i;i=nxt[i])
if(to[i]!=son[u]&&to[i]!=fa[u][0])
dfs1(to[i],to[i]);
if(top[u]==u)
{
int now=u;
while(now)
{
down[u].push_back(now);
now=son[now];
}
now=u;
for(int i=0;i<=maxd[u];i++)
{
up[u].push_back(now);
now=fa[now][0];
}
}
}
inline int jump(int u,int k)
{
if(!k) return u;
u=fa[u][highbit[k]-1];
if(!u) return rt;
k-=pow2[highbit[k]-1];
k-=maxd[top[u]]-maxd[u];
u=top[u];
if(k>=0)
{
if(k<(int)up[u].size()) return up[u][k];
return rt;
}
return down[u][-k];
}
void init()
{
len=B=sqrt(n);
while(B*len<n) len++;
for(re int i=1;i<=B;i++) bll[i]=(i-1)*len+1,blr[i]=i*len;
for(re int i=1;i<=n;i++) bl[i]=(i-1)/len+1;
for(re int i=1;i<=n;i++)
{
if(!vis[bl[i]][a[i]])
{
push(bl[i],i);
minn[bl[i]]=min(minn[bl[i]],dis[a[i]]);
vis[bl[i]][a[i]]=1;
}
}
}
inline void work(const int l,const int r)
{
const int b=bl[l];
for(re int i=l;i<=r;i++)
{
a[i]=fa[a[i]][0];
if(!a[i]) a[i]=rt;
int v=jump(a[i],tag[b]);
if(!vis[b][v])
{
if(!inq[i]) push(b,i);
minn[b]=min(minn[b],dis[v]);
vis[b][v]=1;
}
else if(inq[i]) del(b,inq[i]);
}
}
inline void change(const int l,const int r)
{
const int lb=bl[l],rb=bl[r];
if(lb==rb)
{
work(l,r);
return;
}
work(l,blr[lb]);
work(bll[rb],r);
for(re int b=lb+1;b<rb;b++)
{
tag[b]++;
for(re int j=1;j<=tail[b];j++)
{
const int i=Q[b][j];
const int v=jump(a[i],tag[b]);
if(!vis[b][v])
{
minn[b]=min(minn[b],dis[v]);
vis[b][v]=1;
}
else del(b,j),j--;
}
}
}
inline ll query(const int l,const int r)
{
int lb=bl[l],rb=bl[r];
ll ans=LNF;
if(lb==rb)
{
for(re int i=l;i<=r;i++)
ans=min(ans,dis[jump(a[i],tag[lb])]);
return ans;
}
for(re int i=l;i<=blr[lb];i++)
ans=min(ans,dis[jump(a[i],tag[lb])]);
for(re int i=bll[rb];i<=r;i++)
ans=min(ans,dis[jump(a[i],tag[rb])]);
for(re int i=lb+1;i<rb;i++)
ans=min(ans,minn[i]);
return ans;
}
int main()
{
// freopen("tearssp2.in","r",stdin);
// freopen("tearssp2.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
memset(minn,127,sizeof(minn));
fread(ibuf,1,1<<25,stdin);
n=read(),m=read(),rt=read();
for(re int i=1;i<=n;i++) highbit[i]=highbit[i>>1]+1;
pow2[0]=1;
for(re int i=1;i<=highbit[n];i++) pow2[i]=pow2[i-1]<<1;
for(re int i=1;i<n;i++)
{
int u=read(),v=read(),w=read();
adde(u,v,w),adde(v,u,w);
}
dfs(rt),dfs1(rt,rt);
for(re int i=1;i<=n;i++) a[i]=read();
init();
while(m--)
{
int opt=read(),l=read(),r=read();
if(opt==1) change(l,r);
else out(query(l,r)),*oh++='\n';
}
fwrite(obuf,1,oh-obuf,stdout);
return 0;
}
/*
5 6 2
3 2 2
5 3 3
1 2 4
4 2 3
3 3 3 1 2
2 1 1
2 2 3
2 4 5
1 2 3
1 4 4
2 1 2
*/
/*
10 10 1
9 4 1
5 6 1
2 10 1
6 3 1
1 9 1
1 3 1
6 2 1
1 7 1
8 9 1
2 1 2 9 2 10 9 5 3 2
1 3 7
1 1 7
*/