P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

目录

• 题目
  • 题目背景
  • 题目描述
  • 输入格式
  • 输出格式
  • 输入输出样例
  • 说明/提示
• 思路
• 代码

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

题目

题目背景

题目背景

深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

题目描述

首先村落里的一共有 (n) 座房屋，并形成一个树状结构。然后救济粮分 (m) 次发放，每次选择两个房屋 ((x,~y))，然后对于 (x) 到 (y) 的路径上(含 (x) 和 (y))每座房子里发放一袋 (z) 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

输入格式

输入的第一行是两个用空格隔开的正整数，分别代表房屋的个数 (n) 和救济粮发放的次数 (m)。

第 (2) 到 第 (n) 行，每行有两个用空格隔开的整数 (a,~b)，代表存在一条连接房屋 (a) 和 (b) 的边。

第 ((n + 1)) 到第 ((n + m)) 行，每行有三个用空格隔开的整数 (x,~y,~z)，代表一次救济粮的发放是从 (x) 到 (y) 路径上的每栋房子发放了一袋 (z) 类型的救济粮。

输出格式

输出 (n) 行，每行一个整数，第 (i) 行的整数代表 (i) 号房屋存放最多的救济粮的种类，如果有多种救济粮都是存放最多的，输出种类编号最小的一种。

如果某座房屋没有救济粮，则输出 (0)。

输入输出样例

输入 #1

5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3

输出 #1

2
3
3
0
2

说明/提示

• 对于 (20\%) 的数据，保证 (n, m leq 100)。
• 对于 (50\%) 的数据，保证 (n, m leq 2 imes 10^3)。
• 对于 (100\%) 测试数据，保证 (1 leq n, m leq 10^5)，(1 leq a,b,x,y leq n)，(1 leq z leq 10^5)。

思路

若用(a_{i,j})表示结点(i)上救济粮(j)的数量,则结点(i)的答案就是(k),满足(a_{i,k})最大,(k)最小,即最值所在位置.

我们考虑建一个(a)的(树上)差分数组(b):

[a_{u,i}=b_{u,i}+sum_{vin son(i)}b_{v,i} ]

但是一个(i)一个(i)求,还要维护最值,肯定是爆时空复杂度的.

在看看问题,一次发救济粮,就改了几个数字:(b_{x,z} , b_{y,z} , b_{lca(x,y),z} , b_{fa(lca(x,y)),z})(具体参考树上差分),也就是说(b)数组很多都是空的.所以,我们用 动态开点 + 线段树合并 来维护(a,b),具体看代码.

代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

const int N = 100010;
const int maxZ = 100000;
const int M = 100010;
const int M_logZ = M * 20;

struct EDGE {
	int to , nxt;
} ed[N * 2];
int head[N];
void addedge(int u , int v) {
	static int cnt;
	++cnt;
	ed[cnt].to = v , ed[cnt].nxt = head[u] , head[u] = cnt;
}

int n , m , root;

int father[N];
namespace LCA {//RMQ-LCA,LCA就对了
	int cnt = 0;
	int dep[N * 2] , id[N * 2] , first[N];
	int st[N * 4][25];
	void dfs(int u , int nowdep) {
		++cnt;
		id[cnt] = u , dep[cnt] = nowdep , first[u] = cnt;
		for(int i = head[u] ; i ; i = ed[i].nxt) {
			int v = ed[i].to;
			if(v == father[u])
				continue;
			father[v] = u;
			dfs(v , nowdep + 1);
			++cnt;
			id[cnt] = u , dep[cnt] = nowdep;
		}
	}
	void init(int root) {
		dfs(root , 1);

		for(int i = 1 ; i <= cnt ; i++)
			st[i][0] = i;
		int k = log(n) / log(2) + 1;
		dep[0] = 0x3fffffff;
		for(int j = 1 ; j <= k ; j++)
			for(int i = 1 ; i <= cnt ; i++)
				st[i][j] = dep[st[i][j - 1]] < dep[st[i + (1 << j - 1)][j - 1] ] ? st[i][j - 1] : st[i + (1 << j - 1)][j - 1];

	}
	int lca(int u , int v) {
		u = first[u] , v = first[v];
		if(u > v) {
			int tmp;
			tmp = u , u = v , v = tmp;
		}
		int k = log(v - u + 1) / log(2);
		return id[
		           dep[st[u][k]] < dep[st[v - (1 << k) + 1][k]] ? st[u][k] : st[v - (1 << k) + 1][k]
		       ];
	}
}
inline int dep(int u) {
	return LCA::dep[LCA::first[u]];
}


namespace SegT {//我的一个代码习惯:函数中的p表示当前递归到的线段树结点的编号
	int root[N];
	struct NodeClass {
		int l , r , ls , rs , dat_num , dat_id;
//当前区间[l,r] , ls/rs:LeftSon,RightSon左右子结点编号 , dat_num:区间最值(存放最多的救济粮的数量) ,dat_id:区间最值出现的位置(该救济粮的种类)
	} node[4 * M_logZ];//其实我也不知道数组要开多大QAQ
	inline int newnode (int l , int r) {//开点
		static int cnt = 0;
		++cnt;
		node[cnt].l = l , node[cnt].r = r , node[cnt].dat_id = l;
		return cnt;
	}
	inline void push_up(int p) {//递归子结点后,更新结点p的数据
#define ls(p) node[p].ls
#define rs(p) node[p].rs
		int tmp;
		if(ls(p) == 0)
			tmp = rs(p);
		else if(rs(p) == 0)
			tmp = ls(p);
		else if(node[ls(p)].dat_num >= node[rs(p)].dat_num)//注意等号
			tmp = ls(p);
		else
			tmp = rs(p);
		node[p].dat_id = node[tmp].dat_id , node[p].dat_num = node[tmp].dat_num;
#undef ls
#undef rs
	}
	void change(int p , int pos , int dat) {
		if(node[p].l == node[p].r) {
			node[p].dat_num += dat;
			return;
		}

		int mid = (node[p].l + node[p].r) / 2;
		if(pos <= mid)//这里比较压行,其实就是先检查左/右子树是否为空,若为空,先开一个结点,然后递归
			change(node[p].ls = (node[p].ls == 0 ? newnode(node[p].l , mid) : node[p].ls) , pos , dat);
		else
			change(node[p].rs = (node[p].rs == 0 ? newnode(mid + 1 , node[p].r) : node[p].rs) , pos , dat);
		push_up(p);
	}
	int merge(int p1 , int p2 , int l , int r) {//合并以p1,p2为根的线段树
		if(p1 == 0 || p2 == 0)
			return p1 + p2;
		if(l == r) {
			node[p1].dat_num += node[p2].dat_num;
			return p1;
		}
		int mid = (l + r) / 2;
		node[p1].ls = merge(node[p1].ls , node[p2].ls , l , mid);
		node[p1].rs = merge(node[p1].rs , node[p2].rs , mid + 1 , r);
		push_up(p1);
		return p1;
	}
}


int ans[N];
void calc(int u) {
	for(int i = head[u] ; i ; i = ed[i].nxt) {
		int v = ed[i].to;
		if(v == father[u])
			continue;
		calc(v);
		SegT::root[u] = SegT::merge(SegT::root[u] , SegT::root[v] , 1 , maxZ);
	}
	ans[u] = SegT::node[SegT::root[u]].dat_num == 0 ? 0 : SegT::node[SegT::root[u]].dat_id;
}
int main() {
	n = read() , m = read() , root = 1;
	for(int i = 1 ; i < n ; i++) {
		int u = read() , v = read();
		addedge(u , v) , addedge(v , u);
	}
	LCA::init(root);

	for(int i = 1 ; i <= n ; i++)
		SegT::root[i] = SegT::newnode(1 , maxZ);
	for(int i = 1 ; i <= m ; i++) {
		int u = read() , v = read() , z = read();
		int lca = LCA::lca(u , v);
		SegT::change(SegT::root[u] , z , 1);
		SegT::change(SegT::root[v] , z , 1);
		SegT::change(SegT::root[lca] , z , -1);
		SegT::change(SegT::root[father[lca]] , z , -1);
	}
	calc(root);
	for(int i = 1 ; i <= n ; i++)
		printf("%d
" , ans[i]);
	return 0;
}