一家只做正品的网站,我做的网站关键词到首页了没单子,手机网站前端设计,城乡建设厅官方网站办事大厅F-xay loves trees
考虑在树1中满足条件的一些点#xff0c;首先不难想到一定是一条链#xff0c;其次如果点uuu被选择那么在树2以uuu为根的子树的点就禁止被选#xff0c;于是只需区间#xff0c;然后查询区间最值是否存在1也就是树2中覆盖次数超过2的节点即可。
首…F-xay loves trees
考虑在树1中满足条件的一些点首先不难想到一定是一条链其次如果点uuu被选择那么在树2以uuu为根的子树的点就禁止被选于是只需区间然后查询区间最值是否存在1也就是树2中覆盖次数超过2的节点即可。
首先不难想到可以二分链的长度在树1中进行dfs用双端队列维护维护长度是len的链 2log跑不过。
假如我们dfs到某个点我们假如我们发现长度为len是可以那么我们就可以保存这个长度去维护滑动窗口类似因为答案肯定不会比len还短维护短的没意义那么这个长度就是单调递增的那么这样就没二分了 黑夜和白天大佬题解
Code1 二分
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(Ofast)
#includebits/stdc.h
using namespace std;
using lllong long;
int rd()
{int res0;char chgetchar();while(!isdigit(ch)) {chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res;
}
const int N300010;
int h1[N],e[N2],ne[N2],idx;
int h2[N];
void add(int h[],int a,int b){e[idx]b,ne[idx]h[a],h[a]idx;}
int sz[N],dfn[N];
int n,timestamp;
void dfs1(int u,int fa)
{sz[u]1;dfn[u]timestamp;for(int ih1[u];i!-1;ine[i]){int ve[i];if(vfa) continue;dfs1(v,u);sz[u]sz[v];}
}
int len;
bool ok;
int q[N],tt;
int val[N2],tag[N2];
void pushdown(int u)
{if(tag[u]0) return;tag[u1]tag[u];tag[u1|1]tag[u];val[u1]tag[u];val[u1|1]tag[u];tag[u]0;
}
int dep[N],f2[N];
void dfs3(int u)
{for(int ih2[u];i!-1;ine[i]){int ve[i];if(vf2[u]) continue;dep[v]dep[u]1;f2[v]u;dfs3(v);}
}
void modify(int u,int l,int r,int L,int R,int v)
{if(LlrR) {val[u]v;tag[u]v;return;}pushdown(u);int midlr1;if(Lmid) modify(u1,l,mid,L,R,v);if(Rmid) modify(u1|1,mid1,r,L,R,v);val[u]max(val[u1],val[u1|1]);
}
void dfs2(int u)
{if(ok) return;int curdep[u];if(curlen) {int vq[tt-len1];modify(1,1,n,dfn[v],dfn[v]sz[v]-1,-1);}q[tt]u;modify(1,1,n,dfn[u],dfn[u]sz[u]-1,1);if(cur1len){ll totval[1];if(tot1) ok1;}for(int ih2[u];i!-1;ine[i]){int ve[i];if(vf2[u]) continue;dfs2(v);}--tt;modify(1,1,n,dfn[u],dfn[u]sz[u]-1,-1);if(curlen) {int vq[tt-len1];modify(1,1,n,dfn[v],dfn[v]sz[v]-1,1);}
}
bool check(int x)
{lenx;ok0;tt0;dfs2(1);return ok;
}
void init()
{for(int i1;in;i) h1[i]h2[i]-1;idxtimestamp0;tt0;for(int i1;in;i) dfn[i]sz[i]0;for(int i1;in;i) dep[i]f2[i]0;
}
int main()
{int Tcrd();while(Tc--){nrd();init();for(int i1;in;i){int urd(),vrd();add(h2,u,v);add(h2,v,u);}for(int i1;in;i){int urd(),vrd();add(h1,u,v);add(h1,v,u);}dfs1(1,0);dfs3(1);int l1,r1*max_element(dep1,dep1n);while(lr){int midlr11;if(check(mid)) lmid;else rmid-1;}printf(%d\n,l);}return 0;
}Code2 优化
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(Ofast)
#includebits/stdc.h
using namespace std;
using lllong long;
int rd()
{int res0;char chgetchar();while(!isdigit(ch)) {chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res;
}
const int N300010;
int h1[N],e[N2],ne[N2],idx;
int h2[N];
void add(int h[],int a,int b){e[idx]b,ne[idx]h[a],h[a]idx;}
int sz[N],dfn[N];
int n,timestamp;
void dfs2(int u,int fa)
{sz[u]1;dfn[u]timestamp;for(int ih2[u];i!-1;ine[i]){int ve[i];if(vfa) continue;dfs2(v,u);sz[u]sz[v];}
}
int val[N2],tag[N2];
void pushdown(int u)
{if(tag[u]0) return;tag[u1]tag[u];tag[u1|1]tag[u];val[u1]tag[u];val[u1|1]tag[u];tag[u]0;
}
void modify(int u,int l,int r,int L,int R,int v)
{if(LlrR) {val[u]v;tag[u]v;return;}pushdown(u);int midlr1;if(Lmid) modify(u1,l,mid,L,R,v);if(Rmid) modify(u1|1,mid1,r,L,R,v);val[u]max(val[u1],val[u1|1]);
}
void update(int u,int v){modify(1,1,n,dfn[u],dfn[u]sz[u]-1,v);}
int ans;
int q[N],tt,hh;
void dfs1(int u,int fa)
{int cur-1;q[tt]u;update(u,1);if(val[1]1) ansmax(ans,tt-hh1);else if(tt-hh1ans){curq[hh];update(cur,-1);}for(int ih1[u];i!-1;ine[i]) if(e[i]!fa) dfs1(e[i],u);if(cur!-1) {update(cur,1);q[--hh]cur;}update(u,-1);--tt;
}
void init()
{for(int i1;in;i) h1[i]h2[i]-1;for(int i1;in;i) dfn[i]sz[i]0;for(int i1;i4*n;i) tag[i]val[i]0;idxtimestamphhans0;tt-1;
}
int main()
{int Tcrd();while(Tc--){nrd();init();for(int i1;in;i){int urd(),vrd();add(h1,u,v);add(h1,v,u);}for(int i1;in;i){int urd(),vrd();add(h2,u,v);add(h2,v,u);}dfs2(1,0);dfs1(1,0);printf(%d\n,ans);}return 0;
}
