当前位置:网站首页>P7735-[noi2021] heavy and heavy edges [tree chain dissection, line segment tree]
P7735-[noi2021] heavy and heavy edges [tree chain dissection, line segment tree]
2022-07-06 03:44:00 【QuantAsk】
Preface
On the front line of A I'm writing a blog now
On the subject
Topic link :https://www.luogu.com.cn/problem/P7735
The main idea of the topic
Yes n n n A tree at a point , All edges are light at first , m m m operations .
- hold x → y x\rightarrow y x→y The heavy edges connected by all points on the path become light edges , Then turn the edge on the path into a heavy edge .
- Ask the number of heavy edges on a path .
1 ≤ T ≤ 3 , 1 ≤ n , m ≤ 1 0 5 1\leq T\leq 3,1\leq n,m\leq 10^5 1≤T≤3,1≤n,m≤105
Their thinking
Just find a spot to be the root , We use each point to store the information it connects to its parent node .
Then consider how to operate , Discovery is a path operation on the tree , Consider tree chain subdivision .
* For the convenience of description, we use the light and heavy sides of tree chain partition In bold Describe
First, we can put all the edges on the path ( Information stored at the corresponding point ) Change to double edge , Then the problem lies in how to change the heavy edge of the connection into a light edge .
It is obviously not feasible to modify these edges violently , We notice that we can easily modify the tree chain after splitting Heavy edge , And on a path Light side Not many paths , So we can consider maintaining only the important edge information , We can process the light edge information when we query .
Then it's obvious , about Heavy edge We use the segment tree to modify the information of , And for Light side , We open a segment tree to record the path number of each endpoint covered last time .
If Light side The two endpoints connected are covered by different paths , Then this side is the light side , Otherwise, it is the heavy side .
Time complexity : O ( m log 2 n ) O(m\log^2 n) O(mlog2n)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cctype>
using namespace std;
const int N=1e5+10;
int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-f;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-48;c=getchar();}
return x*f;
}
struct node{
int to,next;
}a[N<<1];
int T,n,m,cnt,tot,ls[N],fa[N],dep[N];
int rfn[N],ed[N],siz[N],son[N],top[N],id[N];
void addl(int x,int y){
a[++tot].to=y;
a[tot].next=ls[x];
ls[x]=tot;return;
}
void dfs(int x){
rfn[x]=++cnt;siz[x]=1;
dep[x]=dep[fa[x]]+1;
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(y==fa[x])continue;
fa[y]=x;dfs(y);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])son[x]=y;
}
ed[x]=cnt;
return;
}
void dFs(int x){
id[x]=++cnt;
if(son[x]){
top[son[x]]=top[x];
dFs(son[x]);
}
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(y==fa[x]||y==son[x])continue;
top[y]=y;dFs(y);
}
return;
}
struct SegTree{
int w[N<<2],lazy[N<<2];
void Clear(){
memset(w,0,sizeof(w));
memset(lazy,0,sizeof(lazy));
return;
}
void Downdata(int x,int l,int r){
if(!lazy[x])return;int mid=(l+r)>>1;
w[x*2]=(mid-l+1)*lazy[x];
w[x*2+1]=(r-mid)*lazy[x];
lazy[x*2]=lazy[x*2+1]=lazy[x];
lazy[x]=0;return;
}
int Ask(int x,int L,int R,int l,int r){
if(L==l&&R==r)return w[x];
int mid=(L+R)>>1;Downdata(x,L,R);
if(r<=mid)return Ask(x*2,L,mid,l,r);
if(l>mid)return Ask(x*2+1,mid+1,R,l,r);
return Ask(x*2,L,mid,l,mid)+Ask(x*2+1,mid+1,R,mid+1,r);
}
void Change(int x,int L,int R,int l,int r,int val){
if(L==l&&R==r){
w[x]=(R-L+1)*val;lazy[x]=val;return;}
int mid=(L+R)>>1;Downdata(x,L,R);
if(r<=mid)Change(x*2,L,mid,l,r,val);
else if(l>mid)Change(x*2+1,mid+1,R,l,r,val);
else Change(x*2,L,mid,l,mid,val),Change(x*2+1,mid+1,R,mid+1,r,val);
w[x]=w[x*2]+w[x*2+1];
}
}Tw,Tl;
void Updata(int x,int y,int pos){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
if(top[x]!=x)Tw.Change(1,1,n,id[top[x]]+1,id[x],1);
Tl.Change(1,1,n,id[top[x]],id[x],pos);
if(son[x])Tw.Change(1,1,n,id[x]+1,id[x]+1,0);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
Tl.Change(1,1,n,id[x],id[y],pos);
if(id[x]!=id[y])Tw.Change(1,1,n,id[x]+1,id[y],1);
if(son[y])Tw.Change(1,1,n,id[y]+1,id[y]+1,0);
if(top[x]!=x)Tw.Change(1,1,n,id[x],id[x],0);
}
bool check(int x){
int p=Tl.Ask(1,1,n,id[x],id[x]);
if(!p)return 0;
return (p==Tl.Ask(1,1,n,id[fa[x]],id[fa[x]]));
}
int Ask(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans+=Tw.Ask(1,1,n,id[top[x]],id[x]);
x=top[x];ans+=check(x);
x=fa[x];
}
if(dep[x]>dep[y])swap(x,y);
if(id[x]!=id[y])ans+=Tw.Ask(1,1,n,id[x]+1,id[y]);
return ans;
}
int main()
{
T=read();
while(T--){
tot=0;
memset(ls,0,sizeof(ls));
memset(fa,0,sizeof(fa));
memset(son,0,sizeof(son));
Tl.Clear();Tw.Clear();
n=read();m=read();
for(int i=1;i<n;i++){
int x=read(),y=read();
addl(x,y);addl(y,x);
}
cnt=0;dfs(1);cnt=0;
top[1]=1;dFs(1);cnt=0;
while(m--){
int op=read(),x=read(),y=read();
if(op==1)++cnt,Updata(x,y,cnt);
else cout<<Ask(x,y)<<'\n';
}
}
return 0;
}
边栏推荐
- ASU & OSU | model based regularized off-line meta reinforcement learning
- C#(三十)之C#comboBox ListView treeView
- mysql从一个连续时间段的表中读取缺少数据
- [rust notes] 18 macro
- Blue style mall website footer code
- 简述C语言中的符号和链接库
- EDCircles: A real-time circle detector with a false detection control 翻译
- [practice] mathematics in lottery
- Python implementation of maddpg - (1) openai maddpg environment configuration
- Microsoft Research, UIUC & Google research | antagonistic training actor critic based on offline training reinforcement learning
猜你喜欢
How to standardize the deployment of automated testing?
数据分析——seaborn可视化(笔记自用)
Align items and align content in flex layout
Force buckle 1189 Maximum number of "balloons"
C#(三十一)之自定义事件
Schnuka: visual positioning system working principle of visual positioning system
canvas切积木小游戏代码
Redo file corruption repair
LTE CSFB test analysis
An article will give you a comprehensive understanding of the internal and external components of "computer"
随机推荐
Microsoft Research, UIUC & Google research | antagonistic training actor critic based on offline training reinforcement learning
BUAA喜鹊筑巢
3.1 detailed explanation of rtthread serial port device (V1)
[Qt5] QT QWidget immediately appears and disappears
施努卡:视觉定位系统 视觉定位系统的工作原理
EDCircles: A real-time circle detector with a false detection control 翻译
C#(二十九)之C#listBox checkedlistbox imagelist
[optimization model] Monte Carlo method of optimization calculation
February 14, 2022 Daily: Google long article summarizes the experience of building four generations of TPU
在字节做测试5年,7月无情被辞,想给划水的兄弟提个醒
多项目编程极简用例
SAP ALV单元格级别设置颜色
【Rust 笔记】18-宏
SAP ALV颜色代码对应颜色(整理)
Mapping between QoE and KQI
How do we make money in agriculture, rural areas and farmers? 100% for reference
2.1 rtthread pin设备详解
canvas切积木小游戏代码
施努卡:什么是视觉定位系统 视觉系统如何定位
[American competition] mathematical terms