题解：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:
- 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} floor), that is, by the result of integer division (y_i div x_j).
- 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) 个操作，操作有两类：
-
给你一个数 (y) ，走一条 (u o dots o v) 的简单路径，每经过一条权为 (x) 的边就令
[large y := lfloor frac{y}{x} floor ]询问最终 (y) 的值。
-
更改某条边的权。
Algorithm
又到了我最喜欢的板子题环节！
而且本题在洛谷的难度评级是NOI/NOI+/CTSC ，快来水黑题吧！
首先注意到有
于是问题转化为询问树上简单路径边权积。
这是个并不困难的问题，可以简单地用树链剖分 + 线段树解决。
具体地，我们首先提出一个点作为根，这样每条边的两端结点就有了父子关系。然后将边权下放到子节点上，将根节点的权赋为1。
这样就将点权转化为了边权。不过要注意统计边权积的时候，不应该记录端点的权（此处指每条链的顶部结点）。
然后跑一下树链剖分，建立线段树即可，只需要写单点修改和区间查询，懒惰标记都不用挂。
然而，观察数据范围，(x_i) 在 (1e18) 的量级，走一条简单路径的乘积最大值可能达到
({10^{18}}^{200000})，你就是写高精度也存不下这玩意，何况要高精度除呢。
等等，除法？
给定 (y) 的值也在 (1e18) 的量级，这意味着 (prod_{i=1}^n x_i) 一旦超过了 (1e18) ，结果就必然为0了。
当然了，两个 (1e18) 乘起来依然会爆 long long ，我们可以
- 正统地，取对数解决。或有精度误差，但影响不大。
- 还有我
__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
", x / res);
else puts("0");
}
else
{
read(a), read(x);
T.update_point(a, x);
}
}
return 0;
}
这板子我还记得怎么写，宝刀未老啊。