遂宁做网站的公司,wordpress 用户管理插件,wordpress 韩国 主题公园,空间 网站都有 肿么做网站LOJ洛谷 这题不就是Peaks(加强版)或者归程么。。这算是\(IOI2018\)撞上\(NOI2018\)的题了#xff1f;\(Kruskal\)重构树#xff08;具体是所有点按从小到大/从大到小的顺序#xff0c;依次加入这些点的边#xff09;#xff0c;我们可以得到两棵树#xff08;和那两题不一…LOJ洛谷 这题不就是Peaks(加强版)或者归程么。。这算是\(IOI2018\)撞上\(NOI2018\)的题了\(Kruskal\)重构树具体是所有点按从小到大/从大到小的顺序依次加入这些点的边我们可以得到两棵树和那两题不一样的是这题的权值在点上不需要新建节点。 对于询问\((S,T,L,R)\)可以倍增找出\(S,T\)可以在哪棵子树中随便走。 那么只需要判断两棵子树是否有交就可以惹。 注意到子树的DFS序是连续的我们可以在第一个子树的某个数据结构上查第二个子树的DFS序区间。用主席树就可以了主席树的下标是每个点在第二棵树上的DFS序。判断第一个子树在第二个子树的DFS序区间中是否有值即可。 写一写权当复习惹。 另外这个题的交互有点逗逼啊...为什么是所有询问一起输出啊 LOJ上15分T掉了不知道为什么应该是交互的问题。不管惹。 //656ms 84.03MB
#include cstdio
#include cctype
#include algorithm
#define BIT 17
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SSTT(TT(SSIN)fread(IN,1,MAXIN,stdin),SSTT)?EOF:*SS)
typedef long long LL;
const int N2e55,M8e55;int n,root[N];
char IN[MAXIN],*SSIN,*TTIN;
struct Graph
{int Enum,H[N],nxt[M],to[M];inline void AE(int u,int v){to[Enum]v, nxt[Enum]H[u], H[u]Enum;to[Enum]u, nxt[Enum]H[v], H[v]Enum;}
}G;
struct Tree
{int fg,fa[N][BIT1],F[N],H[N],nxt[N],L[N],R[N],Index;int Find(int x){return xF[x]?x:F[x]Find(F[x]);}inline void AE(int u,int v){nxt[v]H[u], H[u]v;}inline int Jump(int x,int k){if(fg){for(int iBIT; ~i; --i)if(fa[x][i]fa[x][i]k) xfa[x][i];}else{for(int iBIT; ~i; --i)if(fa[x][i]k) xfa[x][i];}return x;}void DFS(int x,int dep){L[x]Index;for(int i1; 1idep; i) fa[x][i]fa[fa[x][i-1]][i-1];for(int vH[x]; v; vnxt[v]) fa[v][0]x, DFS(v,dep1);R[x]Index;}void Build(const int n){for(int i1; in; i) F[i]i;if(fg){for(int x1,k1; xn; x)for(int iG.H[x],v; i; iG.nxt[i])if((vG.to[i])x){int r1Find(x),r2Find(v);//r1xif(r1!r2){F[r2]r1, AE(r1,r2);if(kn) break;}}}else{for(int xn,k1; x; --x)for(int iG.H[x],v; i; iG.nxt[i])if((vG.to[i])x){int r1Find(x),r2Find(v);if(r1!r2){F[r2]r1, AE(r1,r2);if(kn) break;}}}DFS(fg?n:1,0);}
}T1,T2;
struct Segment_Tree
{#define ls son[x][0]#define rs son[x][1]#define lson ls,son[y][0],l,m#define rson rs,son[y][1],m1,r#define S N*19int tot,sz[S],son[S][2];#undef Svoid Modify(int x,int y,int l,int r,int p){sz[xtot]sz[y]1;if(lr) return;int mlr1;pm?(rsson[y][1],Modify(lson,p)):(lsson[y][0],Modify(rson,p));}int Query(int x,int y,int l,int r,int L,int R)//y-x{if(sz[y]-sz[x]0) return 0;if(Ll rR) return 1;int mlr1;if(Lm)if(mR) return Query(lson,L,R)||Query(rson,L,R);else return Query(lson,L,R);return Query(rson,L,R);}
}T;inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-48,cgc());return now;
}
void DFS(int x)
{static int Index0;Index, T.Modify(root[Index],root[Index-1],1,n,T2.L[x]);for(int vT1.H[x]; v; vT1.nxt[v]) DFS(v);
}int main()
{int nread(),mread(),Qread(); ::nn;for(int i1; im; i) G.AE(read()1,read()1);T1.Build(n), T2.fg1, T2.Build(n), DFS(1);for(int s,t; Q--; )sread()1,tread()1,sT1.Jump(s,read()1),tT2.Jump(t,read()1),putchar(T.Query(root[T1.L[s]-1],root[T1.R[s]],1,n,T2.L[t],T2.R[t])?1:0), putchar(\n);return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/10685264.html
