题目描述
我们要操作的是一条在树上的路径\(s\)->\(t\)。
(1)查询\(s\)->\(t\)最大的数字。
(2)在\(s\)->\(t\)上增加一个数字，输入\(a\)，\(b\),对于路径上的一个点\(u\)增加的数字是\(dis(s, u) \times a + b\)。
解题思路
直接查询一条从\(s\)到\(t\)的路径是十分不方便的，所以我们用树链剖分，这样就是走从\(s\)到\(t\)的所有链，然后维护链上的值，并且一条条查询，然后统一起来就是答案。
于是我们可以自然的想到找\(s\),\(t\)的\(lca\)，因为这样才能拆成两个部分，然后分别维护上面的链。
我们的式子长得像一个一元函数），于是对于每一条单独的链，我们有两种情况。
令\(dis[u]\)表示从根节点到u的距离
(1)\(u\)在\(s\)->\(lca\)
\(add=(dis[s]-dis[u])\times a + b\)
即\(-dis[u] \times a + dis[s]\times a + b\)
(2)\(u\)在\(lca\)->\(t\)
\(add = (dis[s] + dis[u] - 2\times dis[lca]) \times a + b\)
这两个式子都是一个一次函数，而且我们要寻找其中某一个区间的最小值，所以可以使用李超线段树。
关于细节
- 传统的李超线段树是增加一条线段单点查询。对于这个题目，就算是在同一条链上，但是它们的\(dis\)并非是连续的，也就是说李超线段树的\(x\)轴用\(dis\)是不合理的。那么对于一条链而言有什么东西是连续的呢？那就是\(dfn\)，尽管链与链之间的dfn可能不连续，但是我们本身就是单独的维护一条条链，所以这不重要。
- 树链剖分的跳法就是先找到\(lca\)，然后比较\(x\)的\(top\)（也就是链的顶端节点，如果自己就是顶端，那么\(top\)是自己）是否相等，如果相等就不跳了，不相等就继续往上跳(链顶端可以跳到自己的父亲节点)
- 李超线段树存储的是dfn，所以说我们calc具体的函数值时，需要用另外的数组表示对应dfn下的距离。
- 李超线段树是标记永久化的，所以不能只计算最后在满足区间的返回的\(min\)函数值，而是要把经过的所有的区间的都计算一便（这里注意将自己的边界和区间的边界比较，因为是一次函数，所以直接取端点就可以了）。
- 树剖中的点往上跳的时候，点是会被改变的，但是计算所需要的是原来的点，所以要提前存一下）
- st表找最近公共祖先，长度\(n\times 2\)才是边界，不是\(n\)
- 数组不要开小了，st和fp关于st表的是两倍，边是两倍，李超线段树的slo和mn都是四倍，记得开long long
- 李超的时间是\((log_{2}n)^2\)，原因是外面要寻找满足的区间，找到了以后，内部的线段又需要单独更新。树链剖分是\(log_{2}n\)的。我们从下往上走，如果经过了一条轻边，那么我们整个子树的大小会增加至少两倍，那么我们最多经过\(log_{2}n\)条轻边，如果是重链的话，我们可以直接跳过，所以是\(log_{2}n\)的。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
typedef long long ll;
const ll inf = 123456789123456789;
int n, cnt = 0, vis[N], top[N], son[N], dep[N], head[N], dfn[N], st[N << 1][21], len = 0, fp[N], L[N << 1];
int scnt = 0;
ll dis[N], d[N], par[N];
int h = 0;
ll mn[N << 2];
int slo[N << 2];
int m, tot = 0;
struct edge
{
int next, to;
ll w;
}e[N << 1];
struct slope
{
ll k, b;
}sl[N << 1];
void add_edge(int u, int v, int w)
{
e[++ cnt].next = head[u], head[u] = cnt, e[cnt].to = v, e[cnt].w = w;
return ;
}
void add_slope(ll k, ll b)
{
sl[++ scnt].k = k, sl[scnt].b = b;
return ;
}
ll calc(int x, int p)
{
if(p == 0) return inf;
return d[x] * sl[p].k + sl[p].b;
}
bool cmp(ll x, ll y)
{
if(x > y) return true;
return false;
}
int dfs1(int x, int last)
{
int siz = 1, mx = 0;
st[++ len][0] = x, fp[x] = len, par[x] = last;
dep[x] = dep[last] + 1;
for (int i = head[x]; i; i = e[i].next)
{
int y = e[i].to;
if(y == last) continue;
dis[y] = dis[x] + e[i].w;
int s = dfs1(y, x);
if(mx < s) son[x] = y, mx = s;
siz += s;
st[++ len][0] = x;
}
return siz;
}
void dfs2(int x, int last, int ancestor)
{
if(!x) return ;
dfn[x] = ++ tot, d[tot] = dis[x];
top[x] = ancestor, dfs2(son[x], x, ancestor);
for (int i = head[x]; i; i = e[i].next)
{
int y = e[i].to;
if(dfn[y]) continue;
dfs2(y, x, y);
}
return ;
}
void build_st()
{
for (int j = 1; (1 << j) <= len; ++ j)
{
for (int i = 1; i + (1 << j) - 1 <= len; ++ i)
{
int a = st[i][j - 1], b = st[i + (1 << (j - 1))][j - 1];
st[i][j] = dep[a] < dep[b] ? a : b;
}
}
return ;
}
int lca(int x, int y)
{
x = fp[x], y = fp[y];
if(x > y) swap(x, y);
int l = L[y - x + 1];
int a = st[x][l], b = st[y - (1 << l) + 1][l];
return dep[a] < dep[b] ? a : b;
}
void build_tree(int p, int l, int r)
{
mn[p] = inf, slo[p] = 0;
if(l == r) return ;
int mid = (l + r) >> 1;
build_tree(p << 1, l, mid);
build_tree(p << 1 | 1, mid + 1, r);
return ;
}
void update(int p, int l, int r, int u)
{
if(l == r)
{
mn[p] = min(mn[p], calc(l, u));
return ;
}
int &v = slo[p];
int mid = (l + r) >> 1;
if(cmp(calc(mid, v), calc(mid, u))) swap(u, v);
if(cmp(calc(l, v), calc(l, u))) update(p << 1, l, mid, u);
if(cmp(calc(r, v), calc(r, u))) update(p << 1 | 1, mid + 1, r, u);
mn[p] = min(min(min(calc(l, slo[p]), calc(r, slo[p])), mn[p << 1]), mn[p << 1 | 1]);
return ;
}
void add_lichao(int p, int l, int r, int L, int R, int u)
{
if(L <= l && r <= R)
{
update(p, l, r, u);
return ;
}
if(l > R || r < L) return ;
int mid = (l + r) >> 1;
add_lichao(p << 1, l, mid, L, R, u);
add_lichao(p << 1 | 1, mid + 1, r, L, R, u);
mn[p] = min(mn[p], min(mn[p << 1], mn[p << 1 | 1]));
return ;
}
ll query_lichao(int p, int l, int r, int L, int R)
{
if(L <= l && r <= R) return mn[p];
if(l > R || r < L) return inf;
ll ans = min(calc(max(l, L), slo[p]), calc(min(R, r), slo[p]));
int mid = (l + r) >> 1;
return min(min(query_lichao(p << 1, l, mid, L, R), query_lichao(p << 1 | 1, mid + 1, r, L, R)), ans);
}
void add_tree_line(int l, int r, ll k, ll b)
{
add_slope(k, b);
add_lichao(1, 1, n, l, r, scnt);
return ;
}
void add_line(int s, int t, int a, int b)
{
int lc = lca(s, t), S = s;
while(top[s] != top[lc]) add_tree_line(dfn[top[s]], dfn[s], -a, a * dis[S] + b), s = par[top[s]]; //这里有一个and，是为了排除其中一个节点就是lca的情况
add_tree_line(dfn[lc], dfn[s], -a, a * dis[S] + b);
while(top[t] != top[lc]) add_tree_line(dfn[top[t]], dfn[t], a, a * dis[S] - 2 * dis[lc] * a + b), t = par[top[t]];
add_tree_line(dfn[lc], dfn[t], a, a * dis[S] - 2 * dis[lc] * a + b);
return ;
}
ll query(int s, int t)
{
int lc = lca(s, t);
ll ans = inf;
while(top[s] != top[lc]) ans = min(ans, query_lichao(1, 1, n, dfn[top[s]], dfn[s])), s = par[top[s]];
ans = min(ans, query_lichao(1, 1, n, dfn[lc], dfn[s]));
while(top[t] != top[lc]) ans = min(ans, query_lichao(1, 1, n, dfn[top[t]], dfn[t])), t = par[top[t]];
ans = min(ans, query_lichao(1, 1, n, dfn[lc], dfn[t]));
return ans;
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n * 2; ++ i) L[i] = (int)log2(i);
for (int i = 1; i <= n - 1; ++ i)
{
int u, v;
ll w;
scanf("%d %d %lld", &u, &v, &w);
add_edge(u, v, w);
add_edge(v, u, w);
}
dfs1(1, 0);
dfs2(1, 0, 1);
build_st();
build_tree(1, 1, n);
while(m --)
{
int opt;
scanf("%d", &opt);
if(opt == 1)
{
int s, t;
ll a, b;
scanf("%d %d %lld %lld", &s, &t, &a, &b);
add_line(s, t, a, b);
}
else
{
int s, t;
scanf("%d %d", &s, &t);
printf("%lld\n", query(s, t));
}
}
return 0;
}