题目
题解
设$d_x$表示$x$到根的距离，对于每个询问，可以把它拆成
$\sum_{i\in path(u,v)}d_k+d_{p_i}-2d_{LCA(k,p_i)}$
第一个直接$d_k$乘路径长度，第二个可以处理出来$dfs$序上的前缀和，然后跳链统计即可
第三个的统计和这道题差不多
对于一个点$x$，把$P_x$到根都打上标记（边权），这样查询$d_{LCA(k,P_x)}$时就是$k$到根上标记和
因为要在线，所以可以用主席树维护，跳链的时候查询$dfs$序上一段区间在$path(1,k)$上和是多少
复杂度似乎是$O(q{\log n}^3)$的树剖的事，能叫log吗
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=2e5+5;
struct p{
LL x;
int l,r,tags;
}s[MAX*150];
struct q{
int x,y,d;
}c[MAX<<1];
int n,m,num,tot,cnt,Type;
int P[MAX],rt[MAX],h[MAX],w[MAX],id[MAX],top[MAX],son[MAX],siz[MAX],fa[MAX],d[MAX],re[MAX];
LL D[MAX],qwq[MAX],qaq[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void dfs(int x=1,int F=0)
{
d[x]=d[fa[x]=F]+(siz[x]=1);
for(int i=h[x],y;i;i=c[i].x)
if((y=c[i].y)^F)
{
w[y]=c[i].d,D[y]=D[x]+c[i].d,dfs(y,x),siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
void dfs1(int x=1,int tp=1)
{
top[x]=tp,re[id[x]=++cnt]=x;
if(!son[x]) return;
dfs1(son[x],tp);
for(int i=h[x],y;i;i=c[i].x)
if(!id[y=c[i].y]) dfs1(y,y);
}
void add(int x,int y,int d)
{
c[++num]=(q){h[x],y,d},h[x]=num;
c[++num]=(q){h[y],x,d},h[y]=num;
}
void change(int l,int r,int &k,int L,int R)
{
s[++tot]=s[k],k=tot,s[k].x+=qwq[R]-qwq[L-1];
if(l==L&&r==R) return void(++s[k].tags);
if(R<=mid) change(l,mid,tl,L,R);
else if(L>mid) change(mid+1,r,tr,L,R);
else change(l,mid,tl,L,mid),change(mid+1,r,tr,mid+1,R);
}
LL ask(int l,int r,int kl,int kr,int L,int R,int tag=0)
{
if(l==L&&r==R) return s[kr].x-s[kl].x+(qwq[R]-qwq[L-1])*tag;
tag+=s[kr].tags-s[kl].tags;
if(R<=mid) return ask(l,mid,s[kl].l,s[kr].l,L,R,tag);
if(L>mid) return ask(mid+1,r,s[kl].r,s[kr].r,L,R,tag);
return ask(l,mid,s[kl].l,s[kr].l,L,mid,tag)+ask(mid+1,r,s[kl].r,s[kr].r,mid+1,R,tag);
}
LL ask(int x,int y,int k)
{
int cnt=0,K;
LL ans=0;
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
cnt+=id[x]-id[top[x]]+1,ans+=qaq[id[x]]-qaq[id[top[x]]-1],K=k;
while(K) ans-=ask(1,n,rt[id[top[x]]-1],rt[id[x]],id[top[K]],id[K])<<1,K=fa[top[K]];
x=fa[top[x]];
}
if(d[x]>d[y]) swap(x,y);
cnt+=id[y]-id[x]+1,ans+=qaq[id[y]]-qaq[id[x]-1],K=k;
while(K) ans-=ask(1,n,rt[id[x]-1],rt[id[y]],id[top[K]],id[K])<<1,K=fa[top[K]];
return ans+1ll*cnt*D[k];
}
int main()
{
Type=read(),n=read(),m=read();
for(int i=1,x,y;i<n;++i)
x=read(),y=read(),add(x,y,read());
for(int i=1;i<=n;++i)
P[i]=read();
dfs(),dfs1();
for(int i=1;i<=n;++i)
qaq[i]=qaq[i-1]+D[P[re[i]]],qwq[i]=qwq[i-1]+w[re[i]];
for(int i=1,x;i<=n;++i)
{
rt[i]=rt[i-1],x=P[re[i]];
while(x) change(1,n,rt[i],id[top[x]],id[x]),x=fa[top[x]];
}
LL lans=0;
for(int i=1,x,y,k;i<=m;++i)
x=lans*Type^read(),y=lans*Type^read(),k=lans*Type^read(),printf("%lld\n",lans=ask(x,y,k));
return 0;
}
