P5642 人造情感（emotion）
随便挑点杂题做/kk。
乐。
不会做这个题，我难道还不会做 CF856D Masha and Cactus。
先考虑后者怎么做？
CF856D Masha and Cactus
乐。
考虑在 \(LCA\) 上挂很多个 chains.
\[s_u = \sum_{v \in son_u} f_v, f_u = s_u
\]
\[t_i = \underset{(x_i, y_i, w_i)} \max w_i + sum_u - \sum_{z \in path(x_i, y_i), z \ne u} (f_z - sum_z)
\]
\[f_u = \underset{\text LCA(x_i, y_i) = u} \max t_i
\]
这不是很会做吗？？乐/kk
树状数组子树加，查询点到根即可，注意细节，在最后加。
Solution
考虑沿用上一个 Subtask 的想法。
考虑 \(x \to y\) 的路径那么你就考虑字数外的贡献 \(g_u\) 表示删去以 \(u\) 子树的贡献。
什么时候 \(t_{x, y} + g_u\) 会 \(> W(U)\) 呢？我们发现直接拆贡献，求和即可。因为 \(t_{x, y}\) 是按照上一个 subtask 计算的。
然后怎么去做 \(g_u\) 呢？
考虑已经求出了 \(g_u\) 你现在去求 \(g_v\) 。
\[g_v = g_u + sum_u - f_v
\]
\[g_v = \underset{u \in path(x_i, y_i)}\max t_i + g_h - f_v
\]
前面那个很简单啊，树上差分就好了！！但是具体实现可以不用树上差分，不在 \(v\) 这颗子树就好了，一言以蔽之，乐！因为是只取 \(\max\) 的线段树，所以可以直接查找。
那如果 \(h = u\) 呢？又是万恶的类 Journeys 题。
你考虑如果一定要钦定 \(x_i, y_i \ne v\) 的话，那还真的是果咩捏。有一种方法叫做吉老师线段树。但是我们发现那样太麻烦了。可以考虑什么呢？这样的 chains 排序暴力扫即可。怎么证明复杂度？大概就是该子树的链的出现次数。考虑一个 case：那么就是 \(v\) 只会被出现在其子树里的东西卡住。那么要么走 2 steps 要么遍历 chains，复杂度 \(O(\sum |\text{Chains}|)\) 乐。
最后就是寄吧拆贡献。完全学会乐！/fn/fn/fn
感觉技巧性比较强，我仔细往下想那个 \(t_i\) 那个东西应该可以想出来！！（尊嘟假嘟o.O？）。
总结一下，感觉就是拼了个 d1nner 想法的题，感觉不是很难。
方便写：
\[\sum _{LCA(x, y) = u} W(U) - t_{x, y} = w_z + g_{u} + sum_{u} + \sum_{z \in path(x, y), z \ne u} (sum_z - f_z)
\]
那么此时 \(w_z\) 为 0。
\[g_u \times \underset{LCA(x, y) = u} {sum}
\]
\[(sum_z - f_z) * (n - siz_z) * siz_z
\]
估计是这个吧哥。
乱写过样例，乐。乱写过题乐。
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define lc x << 1
#define rc x << 1 | 1
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
const int _ = 3e5 + 5, mod = 998244353;
int n, m, dfc;
int pa[_], son[_], top[_], dep[_], sz[_], dfn[_];
ll f[_], sumf[_], g[_];
void ckmx (ll & x, ll k) { if (x < k) x = k; }
vector <int> e[_];
struct chain {
int x, y;
ll w;
bool operator < (const chain & x) const {
return w > x.w;
}
};
vector <chain> t[_];
namespace BIT {
ll c[_];
void add (int x, ll k) { for ( ; x <= n; x += lowbit(x)) c[x] += k; }
ll querynd (int x) { ll ret = 0; while (x) ret += c[x], x -= lowbit(x); return ret; }
void update (int l, int r, ll k) { add(l, k), add(r + 1, - k); }
} using namespace BIT;
namespace SEG {
ll tr[_ << 2];
void modify (int x, int l, int r, int p, ll k) {
if (l == r) return ckmx(tr[x], k);
int mid = (l + r) >> 1;
p <= mid ? modify(lc, l, mid, p, k) : modify(rc, mid + 1, r, p, k);
tr[x] = max(tr[lc], tr[rc]);
}
ll query (int x, int l, int r, int ql, int qr) {
if (ql > qr) return 0;
if (ql <= l && r <= qr) return tr[x];
int mid = (l + r) >> 1; ll ret = 0;
if (ql <= mid) ckmx(ret, query(lc, l, mid, ql, qr));
if (qr > mid) ckmx(ret, query(rc, mid + 1, r, ql, qr));
return ret;
}
ll querySub (int x, int y) {
return max(query(1, 1, n, dfn[x], dfn[y] - 1), query(1, 1, n, dfn[y] + sz[y], dfn[x] + sz[x] - 1));
}
} using namespace SEG;
void dfs1 (int x, int fa) {
pa[x] = fa;
dep[x] = dep[fa] + 1, sz[x] = 1;
for (int y : e[x]) {
if (y == fa) continue ;
dfs1(y, x), sz[x] += sz[y];
if (sz[y] > sz[son[x]]) son[x] = y;
}
}
void dfs2 (int x, int anc) {
top[x] = anc, dfn[x] = ++ dfc;
if (son[x]) dfs2(son[x], anc);
for (int y : e[x]) if (y ^ pa[x] && y ^ son[x]) dfs2(y, y);
}
int LCA (int x, int y) {
while(top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
x = pa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
void dfs3 (int x) {
for (int y : e[x]) {
if (y == pa[x]) continue ;
dfs3(y), sumf[x] += f[y];
}
f[x] = sumf[x];
int len = t[x].size();
for (auto & [u, v, w] : t[x]) {
w += sumf[x] + querynd(dfn[u]) + querynd(dfn[v]);
ckmx(f[x], w);
}
update(dfn[x], dfn[x] + sz[x] - 1, sumf[x] - f[x]);
}
void dfs4 (int x) {
sort(t[x].begin(), t[x].end());
for (int y : e[x]) {
if (y == pa[x]) continue ;
g[y] = g[x] + sumf[x] - f[y];
for (auto [u, v, w] : t[x]) {
if (LCA(u, y) != y && LCA(v, y) != y) {
ckmx(g[y], g[x] + w - f[y]); break ;
}
}
ckmx(g[y], querySub(x, y) - f[y]);
}
for (auto [u, v, w] : t[x]) modify(1, 1, n, dfn[u], g[x] + w), modify(1, 1, n, dfn[v], g[x] + w);
for (int y : e[x]) if (y ^ pa[x]) dfs4(y);
}
int main() {
/*
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
黛拉可玛莉·岗德森布莱德，一亿年一遇美少女。
*/
cin >> n >> m;
rep(i, 1, n - 1) {
int x, y;
scanf("%d%d", & x, & y);
e[x].push_back(y), e[y].push_back(x);
}
dfs1(1, 0), dfs2(1, 1);
rep(i, 1, m) {
int x, y, w, lca;
scanf("%d%d%d", & x, & y, & w);
lca = LCA(x, y), t[lca].push_back({x, y, w});
}
dfs3(1);
dfs4(1);
ll ans = 1ll * f[1] % mod * n % mod * n % mod;
rep(x, 1, n) {
ll vl = 1, d = 1;
for (int y : e[x]) if (y ^ pa[x]) (d += vl * sz[y] % mod) %= mod, vl += sz[y];
(ans -= (2ll * d - 1 + mod) % mod * ((g[x] % mod + sumf[x] % mod) % mod) % mod), (ans += mod) %= mod;
(ans -= 2ll * sz[x] * (n - sz[x]) % mod * ((sumf[x] - f[x] + mod) % mod) % mod),
(ans += mod) %= mod;
}
cout << ans << endl;
return 0;
}