时间戳

首页 > 技术文章 > 题解：CF593D Happy Tree Party

题解：CF593D Happy Tree Party

Shimarin 2020-09-30 22:34 原文

题解：CF593D Happy Tree Party


Description

Bogdan has a birthday today and mom gave him a tree consisting of \(n\) vertecies. For every edge of the tree \(i\) , some number \(x_i\) was written on it. In case you forget, a tree is a connected non-directed graph without cycles. After the present was granted, \(m\) guests consecutively come to Bogdan's party. When the \(i\)-th guest comes, he performs exactly one of the two possible operations:

  1. Chooses some number \(y_i\) , and two vertecies \(a_i\) and \(b_i\). After that, he moves along the edges of the tree from vertex \(a_i\) to vertex \(b_i\) using the shortest path (of course, such a path is unique in the tree). Every time he moves along some edge \(j\) , he replaces his current number \(y_i\) by \(\large y_i =\lfloor \frac{y_i}{x_j} \rfloor\), that is, by the result of integer division \(y_i \ div \ x_j\).
  2. Chooses some edge \(p_i\) and replaces the value written in it \(x_{p_i}\) by some positive integer \(c_i < x_{p_i}\) .

As Bogdan cares about his guests, he decided to ease the process. Write a program that performs all the operations requested by guests and outputs the resulting value \(y_i\) for each \(i\) of the first type.


数据保证 \(2 \leq n,m \leq 2e5, \ 1 \leq x_i \leq 1e18\)


题意：

给出一棵有边权的树。树上共有 \(n\) 个结点，现在给出 \(m\) 个操作，操作有两类：

  1. 给你一个数 \(y\) ，走一条 \(u \to \dots \to v\) 的简单路径，每经过一条权为 \(x\) 的边就令

    \[\large y := \lfloor \frac{y}{x} \rfloor \]

    询问最终 \(y\) 的值。

  2. 更改某条边的权。


Algorithm

又到了我最喜欢的板子题环节！

而且本题在洛谷的难度评级是NOI/NOI+/CTSC ，快来水黑题吧！


首先注意到有

\[\Large \lfloor \frac {\lfloor \frac {\lfloor \frac {\lfloor \frac{y}{x_1} \rfloor}{x_2} \rfloor} {\vdots} \rfloor} {x_n} \rfloor = \lfloor \frac{y} {\prod _ {i = 1} ^ n x_i} \rfloor \]

于是问题转化为询问树上简单路径边权积。

这是个并不困难的问题，可以简单地用树链剖分 + 线段树解决。

具体地，我们首先提出一个点作为根，这样每条边的两端结点就有了父子关系。然后将边权下放到子节点上，将根节点的权赋为1。

这样就将点权转化为了边权。不过要注意统计边权积的时候，不应该记录端点的权（此处指每条链的顶部结点）。

然后跑一下树链剖分，建立线段树即可，只需要写单点修改和区间查询，懒惰标记都不用挂。


然而，观察数据范围，\(x_i\) 在 \(1e18\) 的量级，走一条简单路径的乘积最大值可能达到

\({10^{18}}^{200000}\)，你就是写高精度也存不下这玩意，何况要高精度除呢。

等等，除法？

给定 \(y\) 的值也在 \(1e18\) 的量级，这意味着 \(\prod_{i=1}^n x_i\) 一旦超过了 \(1e18\) ，结果就必然为0了。

当然了，两个 \(1e18\) 乘起来依然会爆 long long ，我们可以

  1. 正统地，取对数解决。或有精度误差，但影响不大。
  2. 还有我__int128_t 和 long double 解决不了的事吗？ //啊这，CF 用__int128_t 会CE的

于是，开始写代码吧：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int n, m;

template<typename T>
inline void read(T &x)
{
	char c = getchar();	x = 0;
	while(c < '0' || '9' < c)	c = getchar();
	while('0' <= c && c <= '9')
	{
		x = (x << 1) + (x << 3) + c - 48;
		c = getchar();
	}
}

struct Mint {
	long double val;
	Mint():val(1) {}
	Mint(ll x):val(x) {}
	friend Mint operator * (Mint a, Mint b)
	{
		long double ret = a.val * b.val;
		return (ret > 1e18)? 0: ret;
	}
};
Mint &operator *= (Mint &a, Mint b) {
	return a = a * b;
}

template<const int N, const int M>
class Tree {
private:
	int beg[N], nex[M], tar[M], len;
	int dep[N], siz[N], fat[N], hea[N];
	int top[N], dfn[N], id[N], cnt;
	Mint cst[M], vap[N], seg[N << 2];

public:
	Tree():len(1), cnt(0) {}
	inline void add_edge(int a, int b, ll c)
	{
		++len;
		nex[len] = beg[a], beg[a] = len;
		tar[len] = b, cst[len] = c;
	}

	void dfs1(int cur, int pa)
	{
		dep[cur] = dep[pa] + 1;
		fat[cur] = pa, siz[cur] = 1;

		for(int i = beg[cur]; i; i = nex[i])
		{
			if(tar[i] == pa)	continue;
			dfs1(tar[i], cur);
			vap[tar[i]] = cst[i];
			siz[cur] += siz[tar[i]];
			if(hea[cur] == -1 || siz[tar[i]] > siz[hea[cur]])
				hea[cur] = tar[i];
		}
	}

	void dfs2(int cur, int pa)
	{
		top[cur] = pa, ++cnt;
		dfn[cur] = cnt, id[cnt] = cur;

		if(hea[cur] == -1)	return;
		dfs2(hea[cur], pa);

		for(int i = beg[cur]; i; i = nex[i])
			if(tar[i] != hea[cur] && tar[i] != fat[cur])
				dfs2(tar[i], tar[i]);
	}

	#define lson (nod <<1)
	#define rson ((nod <<1) | 1)
	void build(int nod, int lef, int rig)
	{
		if(lef == rig)	seg[nod] = vap[id[lef]];
		else
		{
			int mid = (lef + rig) >> 1;
			build(lson, lef, mid);
			build(rson, mid + 1, rig);
			seg[nod] = seg[lson] * seg[rson];
		}
	}

	inline void init_treecut() {
		memset(hea, -1, sizeof(hea));
		dfs1(1, 0);
		dfs2(1, 1);
		vap[id[1]] = 1;
		build(1, 1, n);
	}

	void update(int nod, int lef, int rig, int goa, Mint val)
	{
		if(lef == rig)	seg[nod] = val;
		else
		{
			int mid = (lef + rig) >> 1;
			if(goa <= mid)	update(lson, lef, mid, goa, val);
			else			update(rson, mid + 1, rig, goa, val);
			seg[nod] = seg[lson] * seg[rson];
		}
	}

	Mint query(int nod, int lef, int rig, int goal, int goar)
	{
		if(goar < lef || rig < goal)	return Mint(1);
		if(goal <= lef && rig <= goar)	return seg[nod];
		Mint ret = 1;
		int mid = (lef + rig) >> 1;
		ret *= query(lson, lef, mid, goal, goar);
		ret *= query(rson, mid + 1, rig, goal, goar);
		return ret;
	}

	Mint query_path(int u, int v)
	{
		Mint ret = 1;
		while(top[u] != top[v])
		{
			if(dep[top[u]] < dep[top[v]])	swap(u, v);
			ret *= query(1, 1, n, dfn[top[u]], dfn[u]);
			u = fat[top[u]];
		}
		if(dfn[u] > dfn[v])	swap(u, v);
		ret *= query(1, 1, n, dfn[u] + 1, dfn[v]);
		return ret;
	}

	void update_point(int x, Mint y)
	{
		int u = tar[x << 1], v = tar[x << 1 | 1];
		if(dep[u] < dep[v])	swap(u, v);
		update(1, 1, n, dfn[u], y);
	}

};

Tree<262144, 524288> T;
int main()
{
	read(n), read(m);

	ll x, res;
	for(int i = 1, u, v; i != n; ++i)
	{
		read(u), read(v), read(x);
		T.add_edge(u, v, x);
		T.add_edge(v, u, x);
	}

	T.init_treecut();
	for(int i = 0, a, b, key; i != m; ++i)
	{
		read(key);
		if(key == 1)
		{
			read(a), read(b), read(x);
			
			res = (ll)T.query_path(a, b).val;
			if(res)	printf("%lld\n", x / res);
			else	puts("0");
		}
		else
		{
			read(a), read(x);
			T.update_point(a, x);
		}
	}
	return 0;
}

这板子我还记得怎么写，宝刀未老啊。

推荐阅读