题解 P3398 【仓鼠找sugar】
大家好，我是个毒瘤，并没有想到什么两路径有重合则两LCA是其中一个LCA这样的神仙结论，只会暴力上数据结构解决。于是我就暴力树剖然后链上查询修改过了这题。
Solution
考虑两条链有相交的部分，等价于把一条链染色以后，查询另一条链上有没有被染色的部分。如果有则有重合，否则没有。
发现染色可以等价于链上权值+1（查询初始权值为0），查询有被染色的则等价于查询链上最大值，如果不为0则有位置被染色
每次查询完后将第一条链上的权值-1，去掉这次查询的贡献，即可做到两次查询互不影响。
于是树剖一下用线段树维护边权即可。
代码十分好写。
Code
#include <cstdio>
#include <algorithm>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endif
#define rg register
#define ci const int
#define cl const long long
typedef long long int ll;
namespace IPT {
const int L = 1000000;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) {
end = buf + fread(front = buf, 1, L, stdin);
if (front == end) return -1;
}
return *(front++);
}
}
template <typename T>
inline void qr(T &x) {
rg char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
if (lst == '-') x = -x;
}
template <typename T>
inline void ReadDb(T &x) {
rg char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar();
if (ch == '.') {
ch = IPT::GetChar();
double base = 1;
while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar();
}
if (lst == '-') x = -x;
}
namespace OPT {
char buf[120];
}
template <typename T>
inline void qw(T x, const char aft, const bool pt) {
if (x < 0) {x = -x, putchar('-');}
rg int top=0;
do {OPT::buf[++top] = x % 10 + '0';} while (x /= 10);
while (top) putchar(OPT::buf[top--]);
if (pt) putchar(aft);
}
const int maxn = 100010;
const int maxm = 200010;
struct Edge {
int to, nxt;
};
Edge edge[maxm]; int hd[maxn], ecnt = 1;
inline void cont(ci from, ci to) {
Edge &e = edge[++ecnt];
e.to = to; e.nxt = hd[from]; hd[from] = ecnt;
}
int n, q, vistime;
int sz[maxn], son[maxn], dfn[maxn], top[maxn], deepth[maxn], fa[maxn];
struct Tree {
Tree *ls, *rs;
int l, r, v, tg;
inline void make_tag(ci _v) {
this->v += _v;
this->tg += _v;
}
inline void pushdown() {
if (!this->tg) return;
if (this->ls) this->ls->make_tag(tg);
if (this->rs) this->rs->make_tag(tg);
this->tg = 0;
}
inline void pushup() {
this->v = this->ls ? (this->rs ? std::max(this->ls->v, this->rs->v) : this->ls->v) : this->rs->v;
}
};
Tree *pool[maxm], qwq[maxm], *rot;
int Top;
void reading();
void dfs(ci, ci);
void DFS(ci, ci);
void buildpool();
void buildroot();
void build(Tree*, ci, ci);
void change(int, int, ci);
void update(Tree*, ci, ci, ci);
bool check(int, int);
int ask(Tree*, ci, ci);
int main() {
freopen("1.in", "r", stdin);
qr(n); qr(q);
reading();
dfs(1,0); DFS(1, 1);
buildpool(); buildroot();
build(rot, 1, n);
int a, b, c, d;
while(q--) {
a = b = c = d = 0;
qr(a); qr(b); qr(c); qr(d);
change(a, b, 1);
if(check(c, d)) puts("Y");
else puts("N");
change(a, b, -1);
}
return 0;
}
void reading() {
int a, b;
for (rg int i = 1; i < n; ++i) {
a = b = 0; qr(a); qr(b);
cont(a, b); cont(b, a);
}
}
void dfs(ci u, ci pree) {
deepth[u] = deepth[fa[u] = edge[pree].to] + 1;
sz[u] = 1;
for (int i = hd[u]; i; i = edge[i].nxt) if (i != pree) {
int &to = edge[i].to;
dfs(to, i ^ 1);
sz[u] += sz[to];
if(sz[to] > sz[son[u]]) son[u] = to;
}
}
void DFS(ci u, ci tp) {
if ((!u) || (dfn[u])) return;
dfn[u] = ++vistime; top[u] = tp;
DFS(son[u], tp);
for (int i = hd[u]; i; i = edge[i].nxt) {
int &to = edge[i].to;
DFS(to, to);
}
}
void buildpool() {
for (rg int i = 0; i < maxm; ++i) pool[i] = qwq + i;
Top = maxm - 1;
}
void buildroot() {
rot = pool[Top--];
}
void build(Tree *u, ci l, ci r) {
u->l = l; u->r = r;
if(l == r) return;
int mid = (l + r) >> 1;
if (l <= mid) build(u->ls = pool[Top--], l, mid);
if (mid < r) build(u->rs = pool[Top--], mid + 1, r);
}
void change(int u, int v, ci p) {
while (top[u] != top[v]) {
if (deepth[top[u]] < deepth[top[v]]) std::swap(u, v);
update(rot, dfn[top[u]], dfn[u], p);
u = fa[top[u]];
}
if (deepth[u] < deepth[v]) std::swap(u, v);
update(rot, dfn[v], dfn[u], p);
}
void update(Tree *u, ci l, ci r, ci v) {
if ((u->l > r) || (u->r < l)) return;
if ((u->l >= l) && (u->r <= r)) {u->make_tag(v);return;}
u->pushdown();
if (u->ls) update(u->ls, l, r, v);
if (u->rs) update(u->rs, l, r, v);
u->pushup();
}
bool check(int u, int v) {
while (top[u] != top[v]) {
if (deepth[top[u]] < deepth[top[v]]) std::swap(u, v);
if (ask(rot, dfn[top[u]], dfn[u])) return true;
u = fa[top[u]];
}
if (deepth[u] < deepth[v]) std::swap(u, v);
return ask(rot, dfn[v], dfn[u]);
}
int ask(Tree *u, ci l, ci r) {
if ((u->l > r) || (u->r < l)) return 0;
if ((u->l >= l) && (u->r <= r)) return u->v;
u->pushdown();
return u->ls ? (u->rs ? std::max(ask(u->ls, l, r), ask(u->rs, l ,r)) : ask(u->ls, l, r)) : ask(u->rs, l, r);
}