考虑用主席树 + 倍增 +dfn 维护
首先，当p\in[l,r]，或者 p 的祖先和子树内均有点x\in[l,r]的时候，答案必为 0。
除去以上情况，这些点要么都在我的祖先的子树（且 p 不在这些子树中）内，要么都在p 的子树内
祖先情况
-
需要找到我的一个祖先点 x 满足：
-
[l,r]的点都不在点 x 的子树内
-
x 是满足第一种情况的最高点
考虑用倍增维护，主席树查询[l,r]上的和即可
其中，主席树对编号开点，以 dfn 作为插入的先后顺序
-
-
或者需要找到一个不处于 p 子树内的点 x 满足：
-
x 为所有y\in[l,r]的 lca
-
点 p 不在 x 的子树内
直接倍增判断是否符合答案即可，最终答案就是 x 到 p 的路径长度
-
子树情况
需要找到 p 的子树内的一个节点 x 满足：
-
[l,r]的点都在点 x 的子树内
-
x 是满足第一种情况的最低点
怎样找到 x？随便挑一个点y\in[l,r]，我要的答案点 x 一定在它到p的路径上
那么直接倍增跳就好了
时间复杂度 O(n \log^2 n)
实现
#include<bits/stdc++.h>
using namespace std;
#define dd ch=getchar()
int read()
{
char dd;int x=0;bool f=false;
while(!isdigit(ch))f|=ch=='-',dd;
while(isdigit(ch))x=x*10+ch-48,dd;
return f?-x:x;
}
#undef dd
void write(int x)
{
if(x<0)x=-x,putchar('-');
if(x>9)write(x/10);
putchar(x%10+48);
}
#define writesp(x) (write(x),putchar(' '))
#define writeln(x) (write(x),putchar('\n'))
const int N=2e5+5;
int n,q;
struct node
{
int v,w,nxt;
}a[N<<1];
int head[N],cnt=0;
void add(int u,int v,int w)
{
a[++cnt].v=v;
a[cnt].w=w;
a[cnt].nxt=head[u];
head[u]=cnt;
}
int tot=0;
int rt[N],t[N*50],ls[N*50],rs[N*50],fa[N][25];
void push_up(int p)
{
t[p]=0;
if(ls[p])t[p]+=t[ls[p]];
if(rs[p])t[p]+=t[rs[p]];
}
int modify(int pre,int l,int r,int pos)
{
int p=++tot;
ls[p]=ls[pre],rs[p]=rs[pre];
if(l==r){t[p]=1;return p;}
int mid=(l+r)>>1;
if(pos<=mid)ls[p]=modify(ls[pre],l,mid,pos);
else rs[p]=modify(rs[pre],mid+1,r,pos);
push_up(p);
return p;
}
int query(int p,int l,int r,int L,int R)
{
if(!p)return 0;
if(L<=l&&r<=R)return t[p];
int mid=(l+r)>>1,ans=0;
if(L<=mid)ans+=query(ls[p],l,mid,L,R);
if(mid<R)ans+=query(rs[p],mid+1,r,L,R);
return ans;
}
int size[N],dep[N],deep[N],dfn[N],num=0;
void dfs(int u)
{
size[u]=1;
dfn[u]=++num;
rt[num]=modify(rt[num-1],1,n,u);
for(int i=1;i<=20;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i;i=a[i].nxt)
{
int v=a[i].v,w=a[i].w;
if(v==fa[u][0])continue;
dep[v]=dep[u]+w;deep[v]=deep[u]+1;
fa[v][0]=u;
dfs(v);
size[u]+=size[v];
}
}
int getres(int x,int l,int r)
{
return query(rt[dfn[x]+size[x]-1],1,n,l,r)-query(rt[dfn[x]-1],1,n,l,r);
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
for(int i=20;i>=0;i--)
if(deep[fa[x][i]]>=deep[y])
x=fa[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int query1(int x,int l,int r)
{
int o=x;
if(getres(o,l,r))return 0;
for(int i=20;i>=0;i--)
if(fa[x][i]&&!getres(fa[x][i],l,r))
x=fa[x][i];
x=fa[x][0];
if(!x)return 0;
return dep[o]-dep[x];
}
int query2(int x,int l,int r)
{
int o=x;x=l;
if(getres(o,l,r)!=r-l+1)return 0;
for(int i=20;i>=0;i--)
if(fa[x][i]&&getres(fa[x][i],l,r)!=r-l+1)
x=fa[x][i];
if(getres(x,l,r)!=r-l+1)x=fa[x][0];
if(!x)return 0;
return dep[x]-dep[o];
}
int query3(int x,int l,int r)
{
int o=x;x=l;
if(getres(o,l,r))return 0;
for(int i=20;i>=0;i--)
if(fa[x][i]&&getres(fa[x][i],l,r)!=r-l+1)
x=fa[x][i];
if(getres(x,l,r)!=r-l+1)x=fa[x][0];
if(!x||getres(x,o,o)==1)return 0;
return dep[o]+dep[x]-dep[lca(x,o)]*2;
}
int main()
{
// freopen("6071.in","r",stdin);
// freopen("6071.out","w",stdout);
n=read(),q=read();
for(int i=1,u,v,w;i<n;i++)
u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);
dfs(1);
int lasans=0;
while(q--)
{
int p=read()^lasans,l=read()^lasans,r=read()^lasans;
writeln(lasans=max(query1(p,l,r),max(query2(p,l,r),query3(p,l,r))));
}
return 0;
}