思路自然的码农题.
显然分类讨论一下编号在 $[l,r]$ 的点与 $p$ 的子树关系.
如果都在 $p$ 的子树内就是个区间 $lca$.
否则，就二分第一个满足 $p$ 的祖先且子树内部没有 $[l,r]$ 之间的点.
二分验证的话要用主席树.
code:
#include <cstring>
#include <map>
#include <algorithm>
#include <cstdio>
#include <vector>
#define N 200008
#define ll long long
#define setIO(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
namespace seg
{
int tot;
int newnode() { return ++tot; }
struct data
{
int sum,ls,rs;
}s[N*50];
void build(int &x,int l,int r)
{
x=newnode();
if(l==r) return;
int mid=(l+r)>>1;
build(s[x].ls,l,mid),build(s[x].rs,mid+1,r);
}
int update(int x,int l,int r,int p,int v)
{
int now=newnode();
s[now]=s[x],s[now].sum=s[x].sum+v;
if(l==r) return now;
int mid=(l+r)>>1;
if(p<=mid) s[now].ls=update(s[x].ls,l,mid,p,v);
else s[now].rs=update(s[x].rs,mid+1,r,p,v);
return now;
}
int query(int x,int y,int l,int r,int L,int R)
{
if(x+y==0) return 0;
if(l>=L&&r<=R) return s[y].sum-s[x].sum;
int re=0,mid=(l+r)>>1;
if(L<=mid) re+=query(s[x].ls,s[y].ls,l,mid,L,R);
if(R>mid) re+=query(s[x].rs,s[y].rs,mid+1,r,L,R);
return re;
}
};
int n,edges,tim;
int hd[N],to[N<<1],nex[N<<1],val[N<<1];
int fa[18][N],dfn[N],st[N],ed[N],rt[N],ge[N],dep[N],dis[N];
void add(int u,int v,int c)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;
}
void dfs(int u,int ff)
{
st[u]=dfn[u]=++tim,ge[tim]=u;
fa[0][u]=ff;
for(int i=1;i<18;++i) fa[i][u]=fa[i-1][fa[i-1][u]];
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(v==ff) continue;
dep[v]=dep[u]+1,dis[v]=dis[u]+val[i];
dfs(v,u);
}
ed[u]=tim;
}
int get_lca(int x,int y)
{
if(dep[x]!=dep[y])
{
if(dep[x]>dep[y]) swap(x,y);
for(int i=17;i>=0;--i) if(dep[fa[i][y]]>=dep[x]) y=fa[i][y];
}
if(x==y) return x;
for(int i=17;i>=0;--i) if(fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
struct node
{
int key;
node() { key=0; }
node operator+(const node &b) const
{
node c;
c.key=get_lca(key,b.key);
return c;
}
}tree[N<<2];
void build(int l,int r,int now)
{
if(l==r) { tree[now].key=l; return; }
int mid=(l+r)>>1;
build(l,mid,now<<1),build(mid+1,r,now<<1|1);
tree[now]=tree[now<<1]+tree[now<<1|1];
}
node query(int l,int r,int now,int L,int R)
{
if(l>=L&&r<=R) return tree[now];
int mid=(l+r)>>1;
if(L<=mid&&R>mid) return query(l,mid,now<<1,L,R)+query(mid+1,r,now<<1|1,L,R);
else if(L<=mid) return query(l,mid,now<<1,L,R);
else return query(mid+1,r,now<<1|1,L,R);
}
int calc(int p,int L,int R)
{
if(seg::query(rt[st[p]-1],rt[ed[p]],1,n,L,R)==R-L+1)
return dis[query(1,n,1,L,R).key]-dis[p];
else if((p>=L&&p<=R)||(seg::query(rt[st[p]-1],rt[ed[p]],1,n,L,R))) return 0;
else
{
int x=p;
// printf("qaq
");
for(int i=17;i>=0;--i)
{
if(fa[i][x]&&seg::query(rt[st[fa[i][x]]-1],rt[ed[fa[i][x]]],1,n,L,R)==0)
x=fa[i][x];
}
int point=fa[0][x];
// 关键节点
int lca=query(1,n,1,L,R).key;
int ans=dis[p]-dis[point]+(dep[lca]>=dep[point]?dis[lca]-dis[point]:0);
return ans;
}
}
int main()
{
// setIO("input");
int i,j,Q;
scanf("%d%d",&n,&Q);
for(i=1;i<n;++i)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c),add(x,y,c),add(y,x,c);
}
dfs(1,0);
build(1,n,1);
seg::build(rt[0],1,n);
for(i=1;i<=n;++i) rt[i]=seg::update(rt[i-1],1,n,ge[i],1);
int lastans=0;
while(Q--)
{
int p,l,r;
scanf("%d%d%d",&p,&l,&r);
p^=lastans,l^=lastans,r^=lastans;
lastans=calc(p,l,r);
printf("%d
",lastans);
}
return 0;
}