做公众号首图网站,命令行连接wordpress,老家装设计网,小米商城网站建设分析正题 题目大意
给出两棵树#xff0c;对于第一棵树的每一条边(x,y)(x,y)(x,y)询问有多少条在第二棵树上的边(u,v)(u,v)(u,v)与其交换#xff08;连接的序号相同#xff09;后两棵树依旧是一棵树。 1≤n≤21051\leq n\leq 2\times 10^51≤n≤2105 解题思路
先只考虑一棵树的…正题 题目大意
给出两棵树对于第一棵树的每一条边(x,y)(x,y)(x,y)询问有多少条在第二棵树上的边(u,v)(u,v)(u,v)与其交换连接的序号相同后两棵树依旧是一棵树。
1≤n≤2×1051\leq n\leq 2\times 10^51≤n≤2×105 解题思路
先只考虑一棵树的合法情况对于第二棵树的边(u,v)(u,v)(u,v)交换过来合法的当且仅当(x,y)(x,y)(x,y)在u→vu\rightarrow vu→v路径上同理的对于第二棵树合法当且仅当(u,v)(u,v)(u,v)在x→yx\rightarrow yx→y路径上。
那么考虑限制一个条件第二个条件用数据结构查询。
我们把所有的(u,v)(u,v)(u,v)用树上差分挂在第一棵树的u→vu\rightarrow vu→v路径上然后遇到一条(u,v)(u,v)(u,v)我们让这棵树的这条边权值111。
这样我们就保证了处理到边(x,y)(x,y)(x,y)时有权值的只有在第一棵树上经过(x,y)(x,y)(x,y)的u→vu\rightarrow vu→v那么至于第二个要求我们直接在第二棵树上查询x→yx\rightarrow yx→y路径上的权值和。这个可以用树链剖分维护。
而树上差分的合并功能就用线段树合并就好了。
时间复杂度O(nlog2n)O(n\log^2n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N2e510,U20;
int n,cnt,depG[N],f[N][U],rt[N],ans[N];
int siz[N],fa[N],dep[N],son[N],top[N],id[N];
vectorpairint,int G[N];
vectorint T[N],v[N];
pairint,int e[N];
struct SegTree{int w[N5],ls[N5],rs[N5];void Change(int x,int L,int R,int pos,int val){if(!x)xcnt;w[x]val;if(LR)return;int mid(LR)1;if(posmid)Change(ls[x],L,mid,pos,val);else Change(rs[x],mid1,R,pos,val);}int Ask(int x,int L,int R,int l,int r){if(!x)return 0;if(LlRr)return w[x];int mid(LR)1;if(rmid)return Ask(ls[x],L,mid,l,r);if(lmid)return Ask(rs[x],mid1,R,l,r);return Ask(ls[x],L,mid,l,mid)Ask(rs[x],mid1,R,mid1,r);}int Merge(int x,int y,int L,int R){if(!x||!y)return x|y;w[x]w[y];if(LR)return x;int mid(LR)1;ls[x]Merge(ls[x],ls[y],L,mid);rs[x]Merge(rs[x],rs[y],mid1,R);return x;}
}S;
void preset(int x,int fa){f[x][0]fa;depG[x]depG[fa]1;for(int i0;iG[x].size();i){int yG[x][i].first;if(yfa)continue;preset(y,x);}return;
}
int LCA(int x,int y){if(depG[x]depG[y])swap(x,y);for(int iU-1;i0;i--)if(depG[f[x][i]]depG[y])xf[x][i];if(xy)return x;for(int iU-1;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];return f[x][0];
}
void dfs1(int x){dep[x]dep[fa[x]]1;siz[x]1;for(int i0;iT[x].size();i){int yT[x][i];if(yfa[x])continue;fa[y]x;dfs1(y);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}return;
}
void dfs2(int x){id[x]cnt;if(son[x]){top[son[x]]top[x];dfs2(son[x]);}for(int i0;iT[x].size();i){int yT[x][i];if(yfa[x]||yson[x])continue;top[y]y;dfs2(y);}return;
}
int GetAns(int x,int y,int rt){int ans0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);ansS.Ask(rt,1,n,id[top[x]],id[x]);xfa[top[x]];}if(dep[x]dep[y])swap(x,y);if(x!y)ansS.Ask(rt,1,n,id[x]1,id[y]);return ans;
}
void solve(int x,int fa,int ids){for(int i0;iG[x].size();i){int yG[x][i].first,idG[x][i].second;if(yfa)continue;solve(y,x,id);rt[x]S.Merge(rt[x],rt[y],1,n);}if(ids){for(int i0;iv[x].size();i){int pabs(v[x][i]);int Xe[p].first,Ye[p].second;if(dep[X]dep[Y])swap(X,Y);S.Change(rt[x],1,n,id[Y],(v[x][i]0)?1:-2);}ans[ids]GetAns(fa,x,rt[x]);}return;
}
int main()
{freopen(exchange.in,r,stdin);freopen(exchange.out,w,stdout);scanf(%d,n);for(int i1;in;i){int x,y;scanf(%d%d,x,y);G[x].push_back(mp(y,i));G[y].push_back(mp(x,i));}for(int i1;in;i){int x,y;scanf(%d%d,x,y);T[x].push_back(y);T[y].push_back(x);e[i]mp(x,y);}preset(1,0);for(int j1;jU;j)for(int i1;in;i)f[i][j]f[f[i][j-1]][j-1];for(int i1;in;i){int xe[i].first,ye[i].second,lcaLCA(x,y);v[x].push_back(i);v[y].push_back(i);v[lca].push_back(-i);}dfs1(1);top[1]1;dfs2(1);solve(1,0,0);for(int i1;in;i)printf(%d ,ans[i]);return 0;
}
