题目描述：
删掉一个边，看其是否联通，图是一棵树，在线，多组询问。
数据范围：
\(n \leq 10^5\)
题解：（休闲一下）
这种直接用dfs序即可，直接讨论连边的位置就行。
还有一种做法懒得打了..就是说考虑维护某一条链上有哪些点，当你询问的时候只要那个询问通道包含这个破坏的通道就能联通，否则就不行，可以开\(vector\)，如果叉特别多，那么每个链的点数就很少，如果叉少，相对的点就多点。
\(dfs\)的时候把\(vector\)里的东西下传即可，可以维护一个方向的特征值（自己随便定义）
#include <bits/stdc++.h>using namespace std;#define io freopen("planets.in","r",stdin),freopen("planets.out","w",stdout)const int MAXN = 1e5 + 10;const int mod = 1e5 + 7;int cnt = 0;struct edge { ???int to; ???int nxt;}e[MAXN << 1];int head[MAXN << 1];int ans[MAXN];void add(int u,int v) { ???e[++cnt].to = v; ???e[cnt].nxt = head[u]; ???head[u] = cnt; ???return;}void Add(int u,int v) { ???add(u,v); ???add(v,u); ???return;}int read () ?{ ???int q=0,f=1;char ch=getchar(); ???while(!isdigit(ch)){ ???????if(ch=='-')f=-1;ch=getchar(); ???} ???while(isdigit(ch)){ ???????q=q*10+ch-'0';ch=getchar(); ???} ???return q*f;}int dfn[MAXN << 1];int idx;int low[MAXN << 1];int dis[MAXN << 1];void dfs(int x) { ???dfn[x] = ++idx; ???for(int i = head[x];i;i = e[i].nxt) { ???????int y = e[i].to; ???????if(!dfn[y]) { ???????????dis[y] = dis[x] + 1; ???????????dfs(y); ???????} ???} ???low[x] = ++idx;}int ok(int top,int x,int y) { ???int st = dfn[top]; ???int ed = low[top]; ???int l = dfn[x]; ???int r = dfn[y]; ???if((st <= l and l <= ed) and (r > ed or r < st)) return 1; ???else if((st <= r and r <= ed) and (l > ed or l < st)) return 1; ???return 0;}int L[MAXN];int R[MAXN];int n,q,c;int main () { ???io; ???n = read(),q = read(),c = read(); ???for(int i = 1;i < n; ++i) { ???????int x = read(),y = read(); ???????Add(x,y); ???????L[i] = x; ???????R[i] = y; ???} ???dfs(1); ???int m = 0; ???for(int i = 1;i <= q; ++i) { ???????int k = read(),x = read(),y = read(); ???????k ^= m;x ^= m;y ^= m; ???????int l = L[k]; ???????int r = R[k]; ???????if(dis[l] < dis[r]) swap(l,r); ???????if(ok(l,x,y)) { ???????????ans[i] = 1; ???????????cout<<"YES"<<endl; ???????} ???????else { ???????????ans[i] = 0; ???????????cout<<"NO"<<endl; ???????} ???????m = (m + (c * (ans[i] + 1) * i % mod) % mod + mod) % mod; ???} ???return 0;}LYOI2018 Hzy's Planets
原文地址：https://www.cnblogs.com/akoasm/p/10121553.html