【洛谷P4556】 雨天的尾巴

题面

题解

线段树合并

我们看到这道题目首先可以想到树上差分，然后\(dfs\)合并

发现题目让我们求的东西很好用线段树维护

于是可以想到线段树合并

全世界只有我写指针版动态开点线段树（大雾

如果你要写指针版，请开内存池，new又耗时又浪费空间

代码

#include<cstdio>

#include<algorithm>

#define RG register

#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);

inline int read()

{

	int data=0, w=1;

	char ch=getchar();

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-') w=-1, ch=getchar();

	while(ch>='0'&&ch<='9') data=data*10+(ch^48), ch=getchar();

	return data*w;

}

const int maxn(100010);

struct node { node *son[2]; int max, id; } *root[maxn], pool[maxn * 50], *pos;

struct edge { int next, to; } e[maxn << 1];

struct query { int next, to, id; } q[maxn << 1];

struct answer { int a, b, v, lca; } ans[maxn];

bool vis[maxn];

int head[maxn], e_num, fa[maxn], n, m, s, qhead[maxn], q_num, F[maxn], Ans[maxn];

inline void add_edge(int from, int to) { e[++e_num] = (edge) {head[from], to}; head[from] = e_num; }

inline void add_query(int from, int to, int id) { q[++q_num] = (query) {qhead[from], to, id}; qhead[from] = q_num; }

inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void dfs(int x)

{

	vis[x] = true;

	for(RG int i = head[x]; i; i = e[i].next)

	{

		int to = e[i].to; if(to == F[x]) continue;

		F[to] = x; dfs(to); fa[find(to)] = find(x);

	}

	for(RG int i = qhead[x]; i; i = q[i].next)

	{

		int to = q[i].to; if(!vis[to]) continue;

		ans[q[i].id].lca = find(to);

	}

}

inline int Max(node *x) { return x ? x -> max : 0; }

inline int Id(node *x) { return x ? x -> id : 0; }

inline void pushup(node *x)

{

	if(Max(x -> son[0]) >= Max(x -> son[1])) x -> max = Max(x -> son[0]), x -> id = Id(x -> son[0]);

	else x -> max = Max(x -> son[1]), x -> id = Id(x -> son[1]);

	if(!x -> max) x -> id = 0;

}

inline void Insert(node *&x, int pos, int val, int l = 1, int r = maxn - 10)

{

	if(!x) x = ::pos++; if(l == r) { x -> max += val; x -> id = l; if(!x -> max) x -> id = 0; return; }

	int mid = (l + r) >> 1;

	if(pos <= mid) Insert(x -> son[0], pos, val, l, mid);

	else Insert(x -> son[1], pos, val, mid + 1, r);

	pushup(x); if(!x -> max) x -> id = 0;

}

inline node *Merge(node *x, node *&y, int l = 1, int r = maxn - 10)

{

	if(!x) return y; if(!y) return x;

	int mid = (l + r) >> 1; if(l == r) { x -> max += y -> max; x -> id = l; return x; }

	x -> son[0] = Merge(x -> son[0], y -> son[0], l, mid);

	x -> son[1] = Merge(x -> son[1], y -> son[1], mid + 1, r);

	pushup(x); return x;

}

void solve(int x)

{

	for(RG int i = head[x]; i; i = e[i].next)

	{

		int to = e[i].to; if(to == F[x]) continue;

		solve(to); root[x] = Merge(root[x], root[to]);

	}

	Ans[x] = Id(root[x]);

}

int main()

{

#ifndef ONLINE_JUDGE

	file(cpp);

#endif

	pos = pool; n = read(); m = read();

	for(RG int i = 1, a, b; i < n; i++) a = read(), b = read(), add_edge(a, b), add_edge(b, a);

	for(RG int i = 1; i <= n; i++) fa[i] = i;

	for(RG int i = 1, a, b, c; i <= m; i++)

		a = read(), b = read(), c = read(), ans[i] = (answer) {a, b, c, 0}, add_query(a, b, i), add_query(b, a, i);

	dfs(1);

	for(RG int i = 1; i <= m; i++)

		Insert(root[ans[i].a], ans[i].v, 1), Insert(root[ans[i].b], ans[i].v, 1), Insert(root[ans[i].lca], ans[i].v, -1),

			Insert(root[F[ans[i].lca]], ans[i].v, -1);

	solve(1); for(RG int i = 1; i <= n; i++) printf("%d\n", Ans[i]);

	return 0;

}