题面
我觉得是签到题
直接分别建出两颗kruskal生成树 然后得到人形/狼形可以到的点集(即为树上的一颗子树)
然后如果两个点集有交集则有解，就在交集任一点变身即可
否则无解
是否有交集首先dfs序搞出来，子树转区间，就变成矩形数点问题
主席树/扫描线加树状数组即可(虽然是交互题但还是可以离线的)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
using namespace std;
struct edge {
int v, nxt;
} e[800010];
int head[400010], tot;
inline void addedge(int u, int v) {
e[++tot] = edge{v, head[u]};
head[u] = tot;
}
int n, m, q;
int fa1[400010], fa2[400010]; // 1 小根 2 大根
vector<int> son1[400010], son2[400010];
int sze1[400010], sze2[400010];
int f1[400010][20], f2[400010][20];
int dfn1[400010], dfn2[400010];
int id1[400010], id2[400010];
inline void dfs1(int now, int f) {
static int dfsnow = 0;
id1[dfn1[now] = ++dfsnow] = now;
sze1[now] = 1;
f1[now][0] = f;
for(auto j : son1[now]) dfs1(j, now), sze1[now] += sze1[j];
}
inline void dfs2(int now, int f) {
static int dfsnow = 0;
id2[dfn2[now] = ++dfsnow] = now;
sze2[now] = 1;
f2[now][0] = f;
for(auto j : son2[now]) dfs2(j, now), sze2[now] += sze2[j];
}
int f[400010], w1[400010], w2[400010];
inline int gf(int a) {return f[a] == a ? a : f[a] = gf(f[a]);}
inline void build() {
memset(f1, -1, sizeof f1);
memset(f2, -1, sizeof f2);
memset(fa1, -1, sizeof fa1);
memset(fa2, -1, sizeof fa2);
for(int i = 0; i < n; i++) w1[i] = w2[i] = i;
for(int i = 0; i < n << 1; i++) f[i] = i;
int lala = n;
for(int i = n - 1; i >= 0; i--) {
for(int j = head[i]; j; j = e[j].nxt) {
if(i > e[j].v) continue;
int x = i, y = e[j].v;
if((x = gf(x)) != (y = gf(y))) {
w1[lala] = min(w1[x], w1[y]);
f[x] = f[y] = lala;
fa1[x] = fa1[y] = lala++;
}
}
}
lala = n;
for(int i = 0; i < n << 1; i++) f[i] = i;
for(int i = 0; i < n; i++) {
for(int j = head[i]; j; j = e[j].nxt) {
if(i < e[j].v) continue;
int x = i, y = e[j].v;
if((x = gf(x)) != (y = gf(y))) {
w2[lala] = max(w2[x], w2[y]);
f[x] = f[y] = lala;
fa2[x] = fa2[y] = lala++;
}
}
}
// printf("%d\n", lala);
// for(int i = 0; i < lala - 1; i++) printf("%d %d\n", fa1[i], fa2[i]);
for(int i = 0; i < lala - 1; i++) son1[fa1[i]].push_back(i);
for(int i = 0; i < lala - 1; i++) son2[fa2[i]].push_back(i);
dfs1(lala - 1, -1);
dfs2(lala - 1, -1);
for(int k = 1; k < 20; k++) {
for(int i = 0; i < lala; i++) if(~f1[i][k - 1]) f1[i][k] = f1[f1[i][k - 1]][k - 1]; else f1[i][k] = -1;
for(int i = 0; i < lala; i++) if(~f2[i][k - 1]) f2[i][k] = f2[f2[i][k - 1]][k - 1]; else f2[i][k] = -1;
}
}
struct node {
node *ls, *rs;
int sum;
} t[8000010];
node *rt[400010];
int cnt = 1;
inline node* newnode(node *x) {
if(x != nullptr) t[cnt] = *x;
return t + cnt++;
}
inline void add(node *(&x), node *old, int l, int r, int k, int v) {
x = newnode(old);
x -> sum += v;
if(l == r) return;
int mid = l + r >> 1;
if(k <= mid) add(x -> ls, x -> ls, l, mid, k, v);
else add(x -> rs, x -> rs, mid + 1, r, k, v);
}
inline int get_sum(node *x, int l, int r, int L, int R) {
if(x == nullptr || l > R || L > r) return 0;
if(L <= l && r <= R) return x -> sum;
int mid = l + r >> 1;
return get_sum(x -> ls, l, mid, L, R) + get_sum(x -> rs, mid + 1, r, L, R);
}
inline int get_sum(int l1, int r1, int l2, int r2) {
return get_sum(rt[r1], 1, n * 2 - 1, l2, r2) - get_sum(rt[l1 - 1], 1, n * 2 - 1, l2, r2);
}
inline void init() {
for(int i = 1; i < n * 2; i++) if(id1[i] < n) add(rt[i], rt[i - 1], 1, n * 2 - 1, dfn2[id1[i]], 1); else rt[i] = rt[i - 1];
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for(int i = 1, u, v; i <= m; i++) scanf("%d%d", &u, &v), addedge(u, v), addedge(v, u);
build();
// for(int i = 0; i < n * 2; i++) printf("%d %d %d %d\n", dfn1[i], sze1[i], dfn2[i], sze2[i]);
init();
for(int i = 1; i <= q; i++) {
int s, t, l, r;
scanf("%d%d%d%d", &s, &t, &l, &r);
if(s < l || t > r) {puts("0"); continue;}
for(int j = 19; j >= 0; j--) if(~f1[s][j] && w1[f1[s][j]] >= l) s = f1[s][j];
for(int j = 19; j >= 0; j--) if(~f2[t][j] && w2[f2[t][j]] <= r) t = f2[t][j];
// printf("%d %d\n", s, t);
if(get_sum(dfn1[s], dfn1[s] + sze1[s] - 1, dfn2[t], dfn2[t] + sze2[t] - 1)) puts("1");
else puts("0");
}
return 0;
}