当前位置:网站首页>[lnoi2014] LCA - tree chain subdivision - multipoint LCA depth and problems
[lnoi2014] LCA - tree chain subdivision - multipoint LCA depth and problems
2022-04-23 09:42:00 【Zimba_】
Templates : Topic link
Advanced : Topic link
The question :
Given a tree n n n A dot tree . q q q Time to ask , Each query gives three values l , r , z l,r,z l,r,z, Ask for ∑ i = l r d e p ( L C A ( i , z ) ) \sum_{i=l}^{r}dep(LCA(i,z)) ∑i=lrdep(LCA(i,z)).
( n < = 1 e 5 , q < = 1 e 5 ) (n<=1e5,q<=1e5) (n<=1e5,q<=1e5)
Ideas :
Consider asking for some a a a Sum point b b b Of L C A LCA LCA depth , We can put some a a a To r o o t root root All points on the path are weighted 1 1 1, Then query points b b b To r o o t root root Their path and are their L C A LCA LCA Depth . Modify... In reverse b b b To r o o t root root The path of , check a a a To r o o t root root The path and are the same .
Then consider multiple points and single points L C A LCA LCA Depth and , You can take each point to r o o t root root All paths add 1 1 1, Then query a single point to r o o t root root The path and .
This becomes the operation of tree chain modification and query , You can use tree chain partition to maintain .
But this question can't be asked every time o ( ( r − l ) l o g 2 n ) o((r-l)log^2n) o((r−l)log2n) Modification of , So we need to find the prefix sum offline , Just take the prefix and subtract it again . Total complexity o ( ( n + q ) l o g 2 n ) o((n+q)log^{2}n) o((n+q)log2n).
Code :
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=201314;
typedef pair<ll,ll> P;
ll tree[1000005],laz[1000005];
void push_down(ll k,ll l,ll r)
{
ll mid=(l+r)/2;
tree[2*k+1]+=laz[k]*(mid-l+1);
laz[2*k+1]+=laz[k];
tree[2*k+2]+=laz[k]*(r-mid);
laz[2*k+2]+=laz[k];
laz[k]=0;
}
ll query(ll k,ll l,ll r,ll x,ll y)
{
if(x<=l&&r<=y)
{
return tree[k];
}
push_down(k,l,r);
ll ans=0,mid=(l+r)/2;
if(x<=mid)ans+=query(2*k+1,l,mid,x,y);
if(y>=mid+1)ans+=query(2*k+2,mid+1,r,x,y);
return ans;
}
void update(ll k,ll l,ll r,ll x,ll y,ll a)
{
if(x<=l&&r<=y)
{
tree[k]+=a*(r-l+1);
laz[k]+=a;
return ;
}
push_down(k,l,r);
ll mid=(l+r)/2;
if(x<=mid)update(2*k+1,l,mid,x,y,a);
if(y>=mid+1)update(2*k+2,mid+1,r,x,y,a);
tree[k]=tree[2*k+1]+tree[2*k+2];
}
vector<ll>v[100005];
ll dep[100005],fa[100005],siz[100005],son[100005];
void dfs1(ll x,ll pre)
{
siz[x]=1;
dep[x]=dep[pre]+1;
fa[x]=pre;
for(ll i=0;i<v[x].size();i++)
{
ll to=v[x][i];
if(to!=pre)
{
dfs1(to,x);
siz[x]+=siz[to];
}
}
son[x]=x;
for(ll i=0;i<v[x].size();i++)
{
ll to=v[x][i];
if(to!=pre)
{
if(son[x]==x||siz[son[x]]<siz[to])son[x]=to;
}
}
}
ll id[100005],idx,top[100005];
void dfs2(ll x,ll pre)
{
if(son[pre]==x)top[x]=top[pre];
else top[x]=x;
id[x]=++idx;
if(son[x]!=x)dfs2(son[x],x);
for(ll i=0;i<v[x].size();i++)
{
ll to=v[x][i];
if(to!=pre&&to!=son[x])
{
dfs2(to,x);
}
}
}
ll n,m;
void add(ll x,ll val)
{
while(top[x]!=1)
{
update(1,1,n,id[top[x]],id[x],val);
x=fa[top[x]];
}
update(1,1,n,id[top[x]],id[x],val);
}
ll get(ll x)
{
if(x==0)return 0;
ll ans=0;
while(top[x]!=1)
{
ans+=query(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
ans+=query(1,1,n,id[top[x]],id[x]);
return ans;
}
map<ll,ll>mp[100005];
vector<P>ve;
struct Q
{
ll l,r,z;
}q[200005];
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=2;i<=n;i++)
{
ll a;
scanf("%lld",&a);
a++;
v[a].push_back(i);
v[i].push_back(a);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=m;i++)
{
ll l,r,z;
scanf("%lld%lld%lld",&l,&r,&z);
l++;r++;z++;
q[i]=Q{
l,r,z};
ve.push_back(P(l-1,z));
ve.push_back(P(r,z));
}
sort(ve.begin(),ve.end());
int cnt=1;
for(int i=0;i<ve.size();i++)
{
while(cnt<=n&&cnt<=ve[i].first)
{
add(cnt,1);
cnt++;
}
mp[ve[i].first][ve[i].second]=get(ve[i].second)%mod;
}
for(int i=1;i<=m;i++)
{
ll l=q[i].l,r=q[i].r,z=q[i].z;
ll ans=mp[r][z]-mp[l-1][z];
printf("%lld\n",(ans%mod+mod)%mod);
}
return 0;
}
版权声明
本文为[Zimba_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230621425343.html
边栏推荐
- 《信息系统项目管理师总结》第八章 项目干系人管理
- Creation of raid0 and RAID5 and Simulation of how RAID5 works
- Go language learning notes - array | go language from scratch
- Two ways for flutter providers to share data
- Personal homepage software fenrus
- How to render web pages
- ASUS laptop can't read USB and surf the Internet after reinstalling the system
- Go language learning notes - exception handling | go language from scratch
- NLLLoss+log_ SoftMax=CE_ Loss
- SAP ECC connecting SAP pi system configuration
猜你喜欢
![Sql1 [geek challenge 2019]](/img/ad/afca09bc1da003393319af700e90e3.png)
Sql1 [geek challenge 2019]

Enter "net start MySQL" and "system error 5. Access denied" appears. Detailed explanation of the problem
![[educational codeforces round 80] problem solving Report](/img/54/2fd298ddce3cd3e28a8fe42b3b8a42.png)
[educational codeforces round 80] problem solving Report

501. Mode in binary search tree

npm ERR! network

Dropout技术之随机神经元与随机深度

Kettle experiment conversion case

Node installation

Leetcode0587. Install fence

DVWA range practice
随机推荐
Sql1 [geek challenge 2019]
golang力扣leetcode 396.旋转函数
Kernel PWN learning (3) -- ret2user & kernel ROP & qwb2018 core
Kettle experiment
The sap export excel file opens and shows that the file format and extension of "XXX" do not match. The file may be damaged or unsafe. Do not open it unless you trust its source. Do you still want to
Golang force buckle leetcode 396 Rotation function
1 + X cloud computing intermediate -- script construction, read-write separation
Kettle实验 (三)
SAP excel has completed file level validation and repair. Some parts of this workbook may have been repaired or discarded.
Employee probation application (Luzhou Laojiao)
(Extended) bsgs and higher order congruence equation
Summary of common concepts and problems of linear algebra in postgraduate entrance examination
SAP pi / PO soap2proxy consumption external WS example
SAP CR transmission request sequence and dependency check
Amazon cloud technology entry Resource Center, easy access to the cloud from 0 to 1
Three challenges that a successful Devops leader should be aware of
Kettle experiment (III)
SQL used query statements
《数字电子技术基础》3.1 门电路概述、3.2 半导体二极管门电路
GUI, CLI and UNIX Philosophy