自己怎么建设一个网站,搜索引擎推广预算,什么是推广员,成都网站建设scjsc888前言
之前线上赛就A的题现在才写博客 正题
题目链接:https://www.luogu.com.cn/problem/P7735 题目大意
有nnn个点的一棵树#xff0c;开始所有边都是轻边#xff0c;mmm次操作。
把x→yx\rightarrow yx→y路径上所有点连接的重边都变为轻边#xff0c;然后再把路径上的…前言
之前线上赛就A的题现在才写博客 正题
题目链接:https://www.luogu.com.cn/problem/P7735 题目大意
有nnn个点的一棵树开始所有边都是轻边mmm次操作。
把x→yx\rightarrow yx→y路径上所有点连接的重边都变为轻边然后再把路径上的边变成重边。询问一条路径上的重边数量。
1≤T≤3,1≤n,m≤1051\leq T\leq 3,1\leq n,m\leq 10^51≤T≤3,1≤n,m≤105 解题思路
前随便找个点当根我们用每个点去储存它连向它父节点边的信息。
然后考虑如何进行操作发现是树上的路径操作考虑树链剖分。
*为了方便描述我们将树链剖分的轻重边用加粗进行描述
首先我们可以先把路径上所有边所对应的点储存的信息都改成重边那么问题就出在我们如何把连接的重边改成轻边。
暴力修改这些边显然不可行我们注意到树链剖分后的我们可以方便的修改重边而一条路径上的轻边路径不多所以我们可以考虑只统一维护重边信息而轻边信息我们可以在查询的时候再处理。
那么做法就很显然了对于重边的信息我们用线段树修改而对于轻边我们再开一个线段树记录每个端点上次被覆盖的路径编号。
如果轻边所连接的两个端点是被不同路径覆盖的那么这条边就是轻边不然就是重边。
时间复杂度O(mlog2n)O(m\log^2 n)O(mlog2n) code
#includecstdio
#includecstring
#includealgorithm
#includeiostream
#includecctype
using namespace std;
const int N1e510;
int read(){int x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-48;cgetchar();}return x*f;
}
struct node{int to,next;
}a[N1];
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].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x){rfn[x]cnt;siz[x]1;dep[x]dep[fa[x]]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[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 ils[x];i;ia[i].next){int ya[i].to;if(yfa[x]||yson[x])continue;top[y]y;dFs(y);}return;
}
struct SegTree{int w[N2],lazy[N2];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(lr)1;w[x*2](mid-l1)*lazy[x];w[x*21](r-mid)*lazy[x];lazy[x*2]lazy[x*21]lazy[x]; lazy[x]0;return;}int Ask(int x,int L,int R,int l,int r){if(LlRr)return w[x];int mid(LR)1;Downdata(x,L,R);if(rmid)return Ask(x*2,L,mid,l,r);if(lmid)return Ask(x*21,mid1,R,l,r);return Ask(x*2,L,mid,l,mid)Ask(x*21,mid1,R,mid1,r);}void Change(int x,int L,int R,int l,int r,int val){if(LlRr){w[x](R-L1)*val;lazy[x]val;return;}int mid(LR)1;Downdata(x,L,R);if(rmid)Change(x*2,L,mid,l,r,val);else if(lmid)Change(x*21,mid1,R,l,r,val);else Change(x*2,L,mid,l,mid,val),Change(x*21,mid1,R,mid1,r,val);w[x]w[x*2]w[x*21];}
}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);xfa[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 pTl.Ask(1,1,n,id[x],id[x]);if(!p)return 0;return (pTl.Ask(1,1,n,id[fa[x]],id[fa[x]]));
}
int Ask(int x,int y){int ans0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);ansTw.Ask(1,1,n,id[top[x]],id[x]);xtop[x];anscheck(x);xfa[x];}if(dep[x]dep[y])swap(x,y);if(id[x]!id[y])ansTw.Ask(1,1,n,id[x]1,id[y]);return ans;
}
int main()
{Tread();while(T--){tot0;memset(ls,0,sizeof(ls));memset(fa,0,sizeof(fa));memset(son,0,sizeof(son));Tl.Clear();Tw.Clear();nread();mread();for(int i1;in;i){int xread(),yread();addl(x,y);addl(y,x);}cnt0;dfs(1);cnt0;top[1]1;dFs(1);cnt0;while(m--){int opread(),xread(),yread();if(op1)cnt,Updata(x,y,cnt);else coutAsk(x,y)\n;}}return 0;
}
