树链剖分+线段树求路径交
树链剖分+线段树求路径交
Gym - 101908L Subway Lines (树链剖分+线段树)
原题链接
题意:
给定一棵树,求a-b的路径和c-d的路径
思路:
树链剖分后,用线段树维护。
在a-b的路径权值全部加1,再查询c-d的区间和就是答案。
每次统计完后记得消除影响。
代码:
#pragma GCC optimize(2)#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int,int>PII;#define I_int ll#define x first#define y second#define PI acos(-1)inline ll read(){ ll 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*10+ch-'0';ch=getchar();} return x*f; }char F[200];inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); cout<<endl; }const int maxn=2e5+100;int n,m,r,mod=1e9+7;int idx,h[maxn],e[maxn],ne[maxn];///链式前向星存int w[maxn],wt[maxn];///初始点权数组int a[maxn<<2],laz[maxn<<2];///线段树数组,懒惰标记数组int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];///son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点int res=0;///查询答案void add(int x,int y){ e[++idx]=y;ne[idx]=h[x];h[x]=idx; }void pushdown(int u,int len){ laz[u<<1]+=laz[u]; laz[u<<1|1]+=laz[u]; a[u<<1]+=laz[u]*(len-(len>>1)); a[u<<1]%=mod; a[u<<1|1]+=laz[u]*(len>>1); a[u<<1|1]%=mod; laz[u]=0; }void build(int u,int l,int r){ if(l==r){ a[u]=wt[l]; if(a[u]>mod) a[u]%=mod; return ; } int mid=(l+r)>>1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); a[u]=(a[u<<1]+a[u<<1|1])%mod; }void query(int u,int l,int r,int L,int R){ if(L<=l&&r<=R){ res+=a[u]; res%=mod; return ; } else{ if(laz[u]) pushdown(u,r-l+1); int mid=(l+r)>>1; if(L<=mid) query(u<<1,l,mid,L,R); if(R>mid) query(u<<1|1,mid+1,r,L,R); } }void update(int u,int l,int r,int L,int R,int k){ if(L<=l&&r<=R){ laz[u]+=k; a[u]+=k*(r-l+1); } else{ int mid=(l+r)>>1; if(laz[u]) pushdown(u,r-l+1); if(L<=mid) update(u<<1,l,mid,L,R,k); if(R>mid) update(u<<1|1,mid+1,r,L,R,k); a[u]=(a[u<<1]+a[u<<1|1])%mod; } }int qRange(int x,int y){ int ans=0; while(top[x]!=top[y]){//当两个点不在同一条链上 if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点 res=0; query(1,1,n,id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和 ans+=res; ans%=mod;//按题意取模 x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点 } //直到两个点处于一条链上 if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点 res=0; query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可 ans+=res; return ans%mod; }inline void updRange(int x,int y,int k){//同上 k%=mod; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); update(1,1,n,id[top[x]],id[x],k); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); update(1,1,n,id[x],id[y],k); }inline int qSon(int x){ res=0; query(1,1,n,id[x],id[x]+siz[x]-1);//子树区间右端点为id[x]+siz[x]-1 return res; }inline void updSon(int x,int k){//同上 update(1,1,n,id[x],id[x]+siz[x]-1,k); }inline void dfs1(int x,int f,int deep){//x当前节点,f父亲,deep深度 dep[x]=deep;//标记每个点的深度 fa[x]=f;//标记每个点的父亲 siz[x]=1;//标记每个非叶子节点的子树大小 int maxson=-1;//记录重儿子的儿子数 for(int i=h[x];i;i=ne[i]){ int y=e[i]; if(y==f)continue;//若为父亲则continue dfs1(y,x,deep+1);//dfs其儿子 siz[x]+=siz[y];//把它的儿子数加到它身上 if(siz[y]>maxson)son[x]=y,maxson=siz[y];//标记每个非叶子节点的重儿子编号 } }inline void dfs2(int x,int topf){//x当前节点,topf当前链的最顶端的节点 id[x]=++cnt;//标记每个点的新编号 wt[cnt]=w[x];//把每个点的初始值赋到新编号上来 top[x]=topf;//这个点所在链的顶端 if(!son[x])return;//如果没有儿子则返回 dfs2(son[x],topf);//按先处理重儿子,再处理轻儿子的顺序递归处理 for(int i=h[x];i;i=ne[i]){ int y=e[i]; if(y==fa[x]||y==son[x])continue; dfs2(y,y);//对于每一个轻儿子都有一条从它自己开始的链 } }int main(){ n=read();m=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); add(u,v);add(v,u); } dfs1(1,0,1); dfs2(1,1); while(m--){ int x=read(),y=read(),xx=read(),yy=read(); updRange(x,y,1); cout<<qRange(xx,yy)<<endl; updRange(x,y,-1); } return 0; }
Gym-102040 F Path Intersection(树链剖分+线段树)
原题链接:
题意:
给定一个由n个节点组成的树,求被k条路径覆盖的边数。
思路:
思路跟上题类似,树链剖分后用线段树维护一下,重点在于如何找到被k条路径都覆盖的边数。
很容易想到的思路是遍历路径上的所有点,记录值为k的个数。
考虑一个性质就是,如果该区间的最大值和最小值都为k的话,那么该区间的点全部有贡献,线段树维护的值增加一下max和min就好了。
代码:
#pragma GCC optimize(2)#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int,int>PII;#define I_int ll#define x first#define y second#define PI acos(-1)inline ll read(){ ll 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*10+ch-'0';ch=getchar();} return x*f; }char F[200];inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); cout<<endl; }const int maxn=2e5+100;int n,m,r,mod=1e9+7;int idx,h[maxn],e[maxn],ne[maxn];///链式前向星存int w[maxn],wt[maxn];///初始点权数组int a[maxn<<2],laz[maxn<<2],Max[maxn<<2],Min[maxn<<2];///线段树数组,懒惰标记数组int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];///son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点int res=0;///查询答案void init(){ memset(w,0,sizeof w); memset(wt,0,sizeof wt); memset(a,0,sizeof a); memset(laz,0,sizeof laz); idx=res=cnt=0; memset(son,0,sizeof son); memset(id,0,sizeof id); memset(fa,0,sizeof fa); memset(dep,0,sizeof dep); memset(siz,0,sizeof siz); memset(top,0,sizeof top); memset(Max,0,sizeof Max); memset(Min,0,sizeof Min); }void add(int x,int y){ e[++idx]=y;ne[idx]=h[x];h[x]=idx; }void pushdown(int u,int len){ laz[u<<1]+=laz[u]; laz[u<<1|1]+=laz[u]; a[u<<1]+=laz[u]*(len-(len>>1)); a[u<<1]%=mod; a[u<<1|1]+=laz[u]*(len>>1); a[u<<1|1]%=mod; laz[u]=0; }void build(int u,int l,int r){ if(l==r){ a[u]=wt[l]; if(a[u]>mod) a[u]%=mod; return ; } int mid=(l+r)>>1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); a[u]=(a[u<<1]+a[u<<1|1])%mod; }void query(int u,int l,int r,int L,int R){ if(L<=l&&r<=R){ res+=a[u]; res%=mod; return ; } else{ if(laz[u]) pushdown(u,r-l+1); int mid=(l+r)>>1; if(L<=mid) query(u<<1,l,mid,L,R); if(R>mid) query(u<<1|1,mid+1,r,L,R); } }void update(int u,int l,int r,int L,int R,int k){ if(L<=l&&r<=R){ laz[u]+=k; a[u]+=k*(r-l+1); } else{ int mid=(l+r)>>1; if(laz[u]) pushdown(u,r-l+1); if(L<=mid) update(u<<1,l,mid,L,R,k); if(R>mid) update(u<<1|1,mid+1,r,L,R,k); a[u]=(a[u<<1]+a[u<<1|1])%mod; } }int qRange(int x,int y){ int ans=0; while(top[x]!=top[y]){//当两个点不在同一条链上 if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点 res=0; query(1,1,n,id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和 ans+=res; ans%=mod;//按题意取模 x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点 } //直到两个点处于一条链上 if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点 res=0; query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可 ans+=res; return ans%mod; }inline void updRange(int x,int y,int k){//同上 k%=mod; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); update(1,1,n,id[top[x]],id[x],k); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); update(1,1,n,id[x],id[y],k); }inline int qSon(int x){ res=0; query(1,1,n,id[x],id[x]+siz[x]-1);//子树区间右端点为id[x]+siz[x]-1 return res; }inline void updSon(int x,int k){//同上 update(1,1,n,id[x],id[x]+siz[x]-1,k); }inline void dfs1(int x,int f,int deep){//x当前节点,f父亲,deep深度 dep[x]=deep;//标记每个点的深度 fa[x]=f;//标记每个点的父亲 siz[x]=1;//标记每个非叶子节点的子树大小 int maxson=-1;//记录重儿子的儿子数 for(int i=h[x];i;i=ne[i]){ int y=e[i]; if(y==f)continue;//若为父亲则continue dfs1(y,x,deep+1);//dfs其儿子 siz[x]+=siz[y];//把它的儿子数加到它身上 if(siz[y]>maxson)son[x]=y,maxson=siz[y];//标记每个非叶子节点的重儿子编号 } }inline void dfs2(int x,int topf){//x当前节点,topf当前链的最顶端的节点 id[x]=++cnt;//标记每个点的新编号 wt[cnt]=w[x];//把每个点的初始值赋到新编号上来 top[x]=topf;//这个点所在链的顶端 if(!son[x])return;//如果没有儿子则返回 dfs2(son[x],topf);//按先处理重儿子,再处理轻儿子的顺序递归处理 for(int i=h[x];i;i=ne[i]){ int y=e[i]; if(y==fa[x]||y==son[x])continue; dfs2(y,y);//对于每一个轻儿子都有一条从它自己开始的链 } } PII pos[maxn];int main(){ int T=read,Case=1; while(T--){ n=read; init(); for(int i=1;i<=n-1;i++){ int u=read,v=read; add(u,v);add(v,u); } dfs1(1,0,1);dfs2(1,1); printf("Case %d\n",Case++); m=read; while(m--){ int k=read; for(int i=1;i<=k;i++){ pos[i].first=read; pos[i].second=read; updRange(pos[i].first,pos[i].second,1); if(i==k){ cout<<qRange(pos[i].first,pos[i].second)<<endl; } } for(int i=1;i<=k;i++){ updRange(pos[i].first,pos[i].second,-1); } } } return 0; }