NC20605. [ZJOI2015]幻想乡战略游戏
描述
傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。
在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。 整个地图是一个树结构，一共有n块空地，这些空地被n-1条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。
在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。 如果补给站在点u上，并且空地v上有dv个单位的军队，那么幽香每天就要花费dv*dist(u,v)的金钱来补给这些军队。
由于幽香需要补给所有的军队，因此幽香总共就要花费为Sigma(Dv*dist(u，v),其中1<=V<=N)的代价。其中dist(u,v)表示u个v在树上的距离（唯一路径的权和）。
因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动他的补给站从而省一些钱。
但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？ 你可以假定一开始所有空地上都没有军队。
输入描述
第一行两个数n和Q分别表示树的点数和幽香操作的个数，其中点从1到n标号。接下来n-1行，每行三个正整数a,b,c，表示a和b之间有一条边权为c的边。接下来Q行，每行两个数u,e，表示幽香在点u上放了e单位个军队（如果e < 0，就相当于是幽香在u上减少了|e|单位个军队，说白了就是du←du+e）。数据保证任何时刻每个点上的军队数量都是非负的。
输出描述
对于幽香的每个操作，输出操作完成以后，每天的最小花费，也即如果幽香选择最优的补给点进行补给时的花费。
示例1
输入:
10 5 1 2 1 2 3 1 2 4 1 1 5 1 2 6 1 2 7 1 5 8 1 7 9 1 1 10 1 3 1 2 1 8 1 3 1 4 1
输出:
0 1 4 5 6
C++11(clang++ 3.9) 解法, 执行用时: 1073ms, 内存消耗: 21112K, 提交时间: 2020-03-15 21:00:26
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define Debug(x) cerr << #x << ": " << x << endl;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
return x * f;
}
const int MAXN = 1e5 + 5;
struct Vtree {
int to[MAXN << 1], len[MAXN << 1], nxt[MAXN << 1], head[MAXN]; int cnte;
int dep[MAXN], fa[MAXN], sz[MAXN], son[MAXN], dis[MAXN], top[MAXN];
inline void addedge(int x, int y, int z) { to[++cnte] = y; len[cnte] = z; nxt[cnte] = head[x]; head[x] = cnte; }
inline int LCA(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
inline int getdis(int x, int y) { return dis[x] + dis[y] - (dis[LCA(x, y)] << 1); }
inline void dfs1(int x, int fth) {
dep[x] = dep[fth] + 1; fa[x] = fth; sz[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i], z = len[i];
if (y != fth) {
dis[y] = dis[x] + z;
dfs1(y, x); sz[x] += sz[y];
if (sz[y] > sz[son[x]]) son[x] = y;
}
}
}
inline void dfs2(int x, int tp) {
top[x] = tp;
if (son[x]) dfs2(son[x], tp);
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i];
if (y != fa[x] && y != son[x]) dfs2(y, y);
}
}
inline void solve() { dfs1(1, 0); dfs2(1, 1); }
} vt;
int fa[MAXN], sz[MAXN], Mx[MAXN]; bool vis[MAXN];
int N, Q, tn, root, rt;
LL sum[MAXN], sumd[MAXN], sumf[MAXN];
vector<pair<int, int>> G[MAXN];
inline void addNew(int x, int y, int z) { G[x].push_back({ y, z }); fa[z] = x; }
inline void getr(int x, int fth) {
sz[x] = 1; Mx[x] = 0;
for (int i = vt.head[x]; i; i = vt.nxt[i]) {
int y = vt.to[i];
if (y != fth && !vis[y]) {
getr(y, x); sz[x] += sz[y];
Mx[x] = max(Mx[x], sz[y]);
}
}
Mx[x] = max(Mx[x], tn - sz[x]);
if (root == 0 || Mx[x] < Mx[root]) root = x;
}
inline void solve(int x) {
vis[x] = true;
for (int i = vt.head[x]; i; i = vt.nxt[i]) {
int y = vt.to[i];
if (!vis[y]) {
tn = sz[y]; root = 0;
getr(y, x); addNew(x, y, root);
solve(root);
}
}
}
inline void Mdf(int x, int y) {
sum[x] += y;
for (int now = x; fa[now]; now = fa[now]) {
int len = vt.getdis(x, fa[now]);
sum[fa[now]] += y; sumd[fa[now]] += (LL)y * len; sumf[now] += (LL)y * len;
}
}
inline LL calc(int x) {
LL ret = sumd[x];
for (int now = x; fa[now]; now = fa[now]) {
int len = vt.getdis(x, fa[now]);
ret += (LL)(sum[fa[now]] - sum[now]) * len;
ret += sumd[fa[now]] - sumf[now];
}
return ret;
}
inline LL Qur(int x) {
LL ret = calc(x);
for (auto now : G[x]) {
LL retc = calc(now.first);
if (retc < ret) return Qur(now.second);
}
return ret;
}
int main() {
N = read(); Q = read();
for (int i = 1; i < N; i++) {
int x = read(), y = read(), z = read();
vt.addedge(x, y, z); vt.addedge(y, x, z);
}
vt.solve();
tn = N; root = 0;
getr(1, 0); rt = root; solve(root);
while (Q--) {
int x = read(), y = read();
Mdf(x, y);
printf("%lld\n", Qur(rt));
}
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 2000ms, 内存消耗: 91748K, 提交时间: 2022-09-24 11:44:17
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <unordered_map>
using namespace std ;
using ll = long long ;
using pii = pair<ll,ll> ;
const int N = 2e5 + 100,M = 2 * N ;
int n,m ;
int h[N],e[M],w[M],ne[M],idx ;
int sz[N],fa[N],pre[N] ;
ll s1[N],s2[N],s[N] ;
unordered_map<int,ll> dist[N] ;
vector<int> grson[N] ;
bool st[N] ;
void add(int a,int b,int c){
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++ ;
}
int getsz(int u,int fa){
int tot = 1 ;
for(int i = h[u] ;~ i ; i = ne[i]){
int j = e[i] ;
if(j == fa || st[j]) continue ;
tot += getsz(j,u) ;
}
return tot ;
}
int getgravity(int u,int fa,int sum){
int gr = -1,mx = 0 ;
sz[u] = 1 ;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(j == fa || st[j]) continue ;
int nx = getgravity(j,u,sum) ;
if(nx != -1) gr = nx ;
sz[u] += sz[j] ;
mx = max(mx,sz[j]) ;
}
mx = max(mx,sum - sz[u]) ;
if(2 * mx <= sum) gr = u ;
return gr ;
}
void dfs(int u,int fa,ll distance,int gr){
dist[gr][u] = distance ;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(j == fa || st[j]) continue ;
dfs(j,u,distance + w[i],gr) ;
}
}
int divtree(int u){
int tot = getsz(u,-1) ;
int gr = getgravity(u,-1,tot) ;
st[gr] = 1 ;
pre[gr] = u ;
for(int i = h[gr] ;~ i ; i = ne[i]){
int j = e[i] ;
if(st[j]) continue ;
dfs(j,gr,w[i],gr) ;
}
for(int i = h[gr] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(st[j]) continue ;
int nx = divtree(j) ;
grson[gr].push_back(nx) ;
fa[nx] = gr ;
}
return gr ;
}
void modify(int u,int e){
for(int i = u ; i ; i = fa[i]){
s[i] += e ;
s1[i] += dist[i][u] * e ;
if(fa[i]) s2[i] += dist[fa[i]][u] * e ;
}
}
ll calc(int x){
ll ans = s1[x] ;
for(int i = x ; fa[i] ; i = fa[i])
ans += s1[fa[i]] - s2[i] + dist[fa[i]][x] * (s[fa[i]] - s[i]) ;
return ans ;
}
ll query(int u){
ll tot = calc(u) ;
for(int x : grson[u]){
ll nx = calc(pre[x]) ;
if(nx < tot) return query(x) ;
}
return tot ;
}
int main(){
scanf("%d%d",&n,&m) ;
memset(h,-1,sizeof h) ;
for(int i = 1 ; i <= n - 1 ;i ++){
int a,b,c ;
scanf("%d%d%d",&a,&b,&c) ;
add(a,b,c),add(b,a,c) ;
}
int rt = divtree(1) ;
while(m--){
int u,e ;
scanf("%d%d",&u,&e) ;
modify(u,e) ;
printf("%lld\n",query(rt)) ;
}
return 0 ;
}