LNOI 2014 LCA

[LNOI2014]LCA

一道擴充思維的好題

一句話題意，給定\(l_{i},r_{i},z_{i}\)，輸出 \(\sum \limits_{j=l_{i}}^{j<=r_{i}}deep(lca(i,z_{i}))\)

多組詢問\(n,m<=50000\)

首先，最暴力的做法肯定是暴力求\(lca\)了，顯然這麼做是無法通過的畢竟是道省選,那麼應該如何處理的？？？？

大緻有兩個方向，一個是優化求解的複雜度，另一個則是将\(deep\)轉化為另一種形式存在

第一種以我的實力無法實作，那麼我們來看一下第二種

思考一下deep的含義到底是什麼？？？？

是深度，但更重要的是這個點到根節點路徑上的點數！！！！

可以回憶一下當時沒有學過\(lca\)的時候是如何求\(lca\)的，讓其中一個點向根節點跳，将經過的點打上标記，然後

再讓另一個點向上跳，跳到第一個被标記的點為止，那麼假如我們讓所有的點都向上跳到根，經過的點的權值全部\(+1\)

那麼查詢一個點到根節點的權值之和就是\(\sum \limits_{i=1}^{i<=n}deep(lca(i,x))\)

#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int maxn=5e4+5;
const int mod=201314;
struct edge{int to,nxt;}e[maxn<<1];
int head[maxn],fa[maxn],top[maxn],siz[maxn],dfn[maxn],dep[maxn],son[maxn],num;
int sum[maxn<<2],lazy[maxn<<2],sze[maxn<<2],n,m,cnt,ans[maxn],jb;
struct node{
	int r,id,flag,x;
	friend bool operator <(node a,node b){
		return a.r<b.r;
	}
}p[maxn<<1];
inline void add(int x,int y)
{
	e[++num]=(edge){y,head[x]};head[x]=num;
	e[++num]=(edge){x,head[y]};head[y]=num;
}
inline void pushdown(int id)
{
	if(!lazy[id]) return;
	sum[lid]+=lazy[id]*sze[lid];
	lazy[lid]+=lazy[id];
	sum[rid]+=lazy[id]*sze[rid];
	lazy[rid]+=lazy[id];
	lazy[id]=0;
}
inline void build(int id,int l,int r)
{
	if(l==r)return sze[id]=1,void();
	int mid=(l+r)>>1;
	build(lid,l,mid);build(rid,mid+1,r);
	sze[id]=sze[lid]+sze[rid];
}
inline void update(int id,int l,int r,int ll,int rr)
{
	if(l>=ll&&r<=rr)
	{lazy[id]++;sum[id]+=sze[id];return ;}
	int mid=(l+r)>>1;pushdown(id);
	if(ll<=mid) update(lid,l,mid,ll,rr);
	if(rr>mid) update(rid,mid+1,r,ll,rr);
	sum[id]=sum[lid]+sum[rid];
}
inline int query(int id,int l,int r,int ll,int rr)
{
	if(l>=ll&&r<=rr)return sum[id];
	int mid=(l+r)>>1,ans=0;pushdown(id);
	if(ll<=mid) ans+=query(lid,l,mid,ll,rr);
	if(rr>mid) ans+=query(rid,mid+1,r,ll,rr);
	return ans;
}
inline void treeup(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		update(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y]) update(1,1,n,dfn[x],dfn[y]);
	else update(1,1,n,dfn[y],dfn[x]);
}
inline int treequery(int x,int y)
{
	int res=0;if(!x) return 0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		res+=query(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y]) res+=query(1,1,n,dfn[x],dfn[y]);
	else res+=query(1,1,n,dfn[y],dfn[x]);
	return res;
}
inline void dfs1(int x,int f)
{
	siz[x]=1;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].to;if(y==f)continue;
		dep[y]=dep[x]+1;fa[y]=x;
		dfs1(y,x);siz[x]+=siz[y];
		if(siz[y]>siz[son[x]])son[x]=y;
	}
}
inline void dfs2(int x,int tp)
{
	top[x]=tp;dfn[x]=++cnt;
	if(!son[x]) return ;
	dfs2(son[x],tp);
	for(int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(y==son[x]||y==fa[x])continue;
		dfs2(y,y);
	}
}
signed main()
{
	n=read();m=read();
	for(int i=2;i<=n;i++)
	{
		int x=read()+1;
		add(x,i);
	}
	for(int i=1;i<=m;i++)
	{
		int x=read()+1,y=read()+1,z=read()+1;
		p[++jb]=(node){x-1,i,-1,z};
		p[++jb]=(node){y,i,1,z};
	}
	dfs1(1,0);dfs2(1,1);int tmp=0;
	build(1,1,n); sort(p+1,p+1+jb);
	for(int i=1;i<=jb;i++)
	{
		while(tmp<p[i].r){tmp++;treeup(1,tmp);}
		ans[p[i].id]+=p[i].flag*treequery(p[i].x,1);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]%mod);
}