LOJ.6073.[2017山东一轮集训Day5]距离(可持久化线段树 树链剖分)

题目链接

---

就是恶心人的，简单写写了...（似乎就是[HNOI2015]开店？）

拆式子，记\(dis_i\)为\(i\)到根节点的路径权值和，\(Ans=\sum dis_{p_i}+\sum dis_k-2\sum dis_{LCA(p_i,k)}\)。\(\sum dis_{LCA(p_i,k)}\)的求法类似[LNOI2014]LCA，在每个\(u\to v\)路径上，每个\(p_i\)到根节点的路径上权值\(+1\)（本题就是下放点权，每次所有点的\(sum\)加上它的点权），然后求一遍\(k\)到根节点的路径权值和就是答案。

为了方便，再差分，原修改是\(\sum_{i\in(u,v)}i\to root\)，变成\(\sum_{i\in(u,root)}i\to root+\sum_{i\in(v,root)}i\to root\\-\sum_{i\in(LCA(u,v),root)}i\to root-\sum_{i\in fa[(LCA(u,v)],root)}i\to root\)。

对每个点\(x\)建一棵可持久化线段树，每次在这棵树上修改\(p_x\)到\(root\)的路径，就可以了。

需要树剖，也就是区间修改，可以标记永久化。

查询就在四棵线段树上查。复杂度\((n+q)\log^2n\)。

---

//5869ms	213632K

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 300000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=2e5+5;

int n,P[N],Enum,H[N],nxt[N<<1],to[N<<1],len[N<<1],dep[N],fa[N],sz[N],son[N],top[N],dfn[N],ref[N],root[N];

LL w[N],dis[N],sump[N];

char IN[MAXIN],*SS=IN,*TT=IN;

struct Segment_Tree

{

	#define ls son[x][0]

	#define rs son[x][1]

	#define lson ls,l,m

	#define rson rs,m+1,r

	#define S N*100

	int tot,son[S][2],tm[S];

	LL sum[S];

	#undef S

	void Modify(int &x,int y,int l,int r,int L,int R)

	{

		sum[x=++tot]=sum[y], tm[x]=tm[y], ls=son[y][0], rs=son[y][1];

		if(L<=l && r<=R) {++tm[x]; return;}

		sum[x]=sum[y]+w[std::min(r,R)]-w[std::max(l,L)-1];

		int m=l+r>>1;

		if(L<=m) Modify(ls,son[y][0],l,m,L,R);

		if(m<R) Modify(rs,son[y][1],m+1,r,L,R);

	}

	LL Query(int x,int l,int r,int L,int R)

	{

		if(!x) return 0;

		LL res=tm[x]*(w[std::min(r,R)]-w[std::max(l,L)-1]);

		if(L<=l && r<=R) return sum[x]+res;

		int m=l+r>>1;

		if(L<=m) res+=Query(lson,L,R);

		if(m<R) res+=Query(rson,L,R);

		return res;

	}

}T;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-48,c=gc());

	return now;

}

inline void AE(int w,int v,int u)

{

	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;

	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;

}

inline int LCA(int u,int v)

{

	while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];

	return dep[u]>dep[v]?v:u;

}

void DFS1(int x)

{

	int mx=0; sz[x]=1;

	for(int i=H[x],v; i; i=nxt[i])

		if((v=to[i])!=fa[x])

			fa[v]=x, dep[v]=dep[x]+1, dis[v]=dis[x]+len[i], DFS1(v), sz[x]+=sz[v], sz[v]>mx&&(mx=sz[v],son[x]=v);

}

void DFS2(int x,int tp)

{

	static int Index=0;

	top[x]=tp, ref[dfn[x]=++Index]=x, sump[x]=sump[fa[x]]+dis[P[x]];//son!

	if(son[x])

	{

		DFS2(son[x],tp);

		for(int i=H[x],v; i; i=nxt[i])

			if((v=to[i])!=fa[x])

			{

				if(v!=son[x]) DFS2(v,v);

				w[dfn[v]]=len[i];//son!

			}

	}

}

void Modify(int x)

{

	int p=P[x]; root[x]=root[fa[x]];

	while(p>1) T.Modify(root[x],root[x],1,n,dfn[top[p]],dfn[p]), p=fa[top[p]];

}

LL Query(int k,int rt)

{

	if(!rt) return 0;

	LL ans=0;

	while(k>1) ans+=T.Query(rt,1,n,dfn[top[k]],dfn[k]), k=fa[top[k]];

	return ans;

}

int main()

{

//	freopen("C.in","r",stdin);

//	freopen("C.out","w",stdout);

	const int type=read(),n=read(),q=read(); ::n=n;

	for(int i=1; i<n; ++i) AE(read(),read(),read());

	for(int i=1; i<=n; ++i) P[i]=read();

	dep[1]=1, DFS1(1), DFS2(1,1);

	for(int i=1; i<=n; ++i) w[i]+=w[i-1];

	for(int i=1; i<=n; ++i) Modify(ref[i]);

	LL ans=0;

	for(int i=1; i<=q; ++i)

	{

		int u=read(),v=read(),k=read();

		if(type) u^=ans, v^=ans, k^=ans;

		int w=LCA(u,v),tot=dep[u]+dep[v]-(dep[w]<<1)+1;

		ans=tot*dis[k]+sump[u]+sump[v]-sump[w]-sump[fa[w]];

		LL tmp=Query(k,root[u])+Query(k,root[v])-Query(k,root[w])-Query(k,root[fa[w]]);

		printf("%lld\n",ans-=tmp<<1);

	}

	return 0;

}