[HDU6271]Master of Connected Component
题目大意:
给出两棵(n(nle10000))个结点的以(1)为根的树(T_a,T_b),和一个拥有(m(mle10000))个结点的图(G)。(T_a,T_b)的每一个结点上都有一个信息,表示(G)中的一条边((u_i,v_i))。对于(iin[1,n]),询问从(T_a)和(T_b)上分别取出链(1sim i),将链上的信息所表示的边加入(G)中后,(G)中共有多少连通块。
思路:
对于(T_a)分块,对于(T_a)中的每一块,在(T_b)上DFS,若当前结点是(T_a)当前块内结点,则暴力加入(T_b)中所需要的边进行统计。加边、删边操作用栈记录并查集合并情况,并查集只按秩合并,不路径压缩,实现可拆分并查集。时间复杂度(O(nsqrt nlog n))。
源代码:
#include<cmath>
#include<stack>
#include<cstdio>
#include<cctype>
#include<vector>
#include<numeric>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
constexpr int N=10001;
int n,m,lim,ans[N],par[2][N],dep[N],dfn[N];
std::pair<int,int> w[2][N];
std::vector<int> e[2][N];
inline void clear() {
dfn[0]=0;
for(register int t=0;t<2;t++) {
for(register int i=1;i<=n;i++) {
e[t][i].clear();
e[t][i].shrink_to_fit();
}
}
std::fill(&ans[1],&ans[n]+1,0);
}
int top;
std::pair<int*,int> stack[N*4];
inline void push(int &x) {
stack[++top]={&x,x};
}
inline void back(const int &tmp) {
for(;tmp<top;top--) {
*stack[top].first=stack[top].second;
}
}
class DisjointSet {
private:
int anc[N],size[N];
int find(const int &x) {
return x==anc[x]?x:find(anc[x]);
}
public:
void reset() {
std::iota(&anc[1],&anc[m+1],1);
std::fill(&size[1],&size[m+1],1);
}
void merge(const int &x,const int &y) {
int p=find(x),q=find(y);
if(p==q) return;
if(size[p]>size[q]) std::swap(p,q);
push(anc[p]);
push(size[q]);
anc[p]=q;
size[q]+=size[p];
}
};
DisjointSet s;
void solve(const int &x,const int &t) {
const int tmp=top;
s.merge(w[1][x].first,w[1][x].second);
if(ans[x]==-1&&dfn[x]>=dfn[t]) {
const int tmp=top;
for(register int y=x;y!=t;y=par[0][y]) {
s.merge(w[0][y].first,w[0][y].second);
}
ans[x]=m-top/2;
back(tmp);
}
for(auto &y:e[1][x]) {
solve(y,t);
}
back(tmp);
}
void dfs(const int &x) {
const int tmp=top;
s.merge(w[0][x].first,w[0][x].second);
dep[x]=1;
dfn[x]=++dfn[0];
for(auto &y:e[0][x]) {
dfs(y);
dep[x]=std::max(dep[x],dep[y]+1);
}
ans[x]=-1;
if(dep[x]==lim||x==1) {
solve(1,x);
dep[x]=0;
}
back(tmp);
}
int main() {
for(register int T=getint();T;T--) {
n=getint(),m=getint(),lim=sqrt(n);
for(register int t=0;t<2;t++) {
for(register int i=1;i<=n;i++) {
w[t][i]={getint(),getint()};
}
for(register int i=1;i<n;i++) {
const int u=getint(),v=getint();
par[t][v]=u;
e[t][u].push_back(v);
}
}
s.reset();
dfs(1);
for(register int i=1;i<=n;i++) {
printf("%d
",ans[i]);
}
clear();
}
return 0;
}