题目描述
傲娇少女幽香正在玩一个非常有趣的战略类游戏,本来这个游戏的地图其实还不算太大,幽香还能管得过来,但是不知道为什么现在的网游厂商把游戏的地图越做越大,以至于幽香一眼根本看不过来,更别说和别人打仗了。
在打仗之前,幽香现在面临一个非常基本的管理问题需要解决。
整个地图是一个树结构,一共有块空地,这些空地被
条带权边连接起来,使得每两个点之间有一条唯一的路径将它们连接起来。在游戏中,幽香可能在空地上增加或者减少一些军队。同时,幽香可以在一个空地上放置一个补给站。 如果补给站在点
上,并且空地
上有
个单位的军队,那么幽香每天就要花费
的金钱来补给这些军队。由于幽香需要补给所有的军队,因此幽香总共就要花费为
的代价。其中
表示
个
在树上的距离(唯一路径的权和)。
因为游戏的规定,幽香只能选择一个空地作为补给站。在游戏的过程中,幽香可能会在某些空地上制造一些军队,也可能会减少某些空地上的军队,进行了这样的操作以后,出于经济上的考虑,幽香往往可以移动他的补给站从而省一些钱。但是由于这个游戏的地图是在太大了,幽香无法轻易的进行最优的安排,你能帮帮她吗? 你可以假定一开始所有空地上都没有军队。
输入格式
第一行两个数和
分别表示树的点数和幽香操作的个数,其中点从1到
标号。 接下来
行,每行三个正整数
,表示
和
之间有一条边权为
的边。
接下来行,每行两个数
,表示幽香在点
上放了
单位个军队(如果
,就相当于是幽香在
上减少了
单位个军队,说白了就是
)。数据保证任何时刻每个点上的军队数量都是非负的。
输出格式
对于幽香的每个操作,输出操作完成以后,每天的最小花费,也即如果幽香选择最优的补给点进行补给时的花费。
题目解析
据说数据比较弱,可以过十万,不明觉厉~
考虑点分治。我们将分治结构建成一棵分治树,在每个结点维护分治结构内的点权和,带权距离和。修改时只会影响到层结点,简单维护一下就好,复杂度
。询问时我们从根出发,先看一下当前点是否是带权重心,如果不是,那么重心一定在带权距离和最大的分治子结构里。询问一次某点的带权距离和
,经过的点有
层,故复杂度为
。总时间复杂度
。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
/************************************************************** Problem: 3924 User: frank_c1 Language: C++ Result: Accepted Time:25232 ms Memory:112332 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct edge { int next,to,adj;LL dist; }; const int maxn=(int)(2e5)+5; const int INF=(int)(1e9); int fr[maxn]; int hd[maxn]; int fa[maxn]; int siz[maxn]; LL dst[maxn]; LL dtf[maxn][50]; LL sv[maxn],sva[maxn]; LL dsv[maxn],dsva[maxn]; bool vis[maxn]; edge e[maxn<<1]; edge lk[maxn<<1]; int misiz,totsiz,rt; int n,tote=0,totk=0; inline void addone(int u,int v,LL d) { ++tote; e[tote].next=fr[u];fr[u]=tote;e[tote].to=v;e[tote].dist=d; } inline void addedge(int u,int v,LL d) { addone(u,v,d);addone(v,u,d); } inline void addlink(int u,int v,int a) { ++totk; lk[totk].next=hd[u];hd[u]=totk;lk[totk].to=v;lk[totk].adj=a; } void findroot(int x,int f) { siz[x]=1;int tmp=0; RAL(i,x) if(e[i].to!=f && !vis[e[i].to]) { findroot(e[i].to,x); siz[x]+=siz[e[i].to]; tmp=max(tmp,siz[e[i].to]); } tmp=max(tmp,totsiz-siz[x]); if(misiz>tmp) misiz=tmp,rt=x; } void dfs(int x,int f) { dtf[x][++dtf[x][0]]=dst[x]; RAL(i,x) if(!vis[e[i].to] && e[i].to!=f) { dst[e[i].to]=dst[x]+e[i].dist; dfs(e[i].to,x); } } int tdc(int x,int f) { misiz=INF; findroot(x,0);x=rt;fa[x]=f; vis[x]=1; findroot(x,0); RAL(i,x) if(!vis[e[i].to]) { totsiz=siz[e[i].to]; addlink(x,tdc(e[i].to,x),e[i].to); dst[e[i].to]=e[i].dist; dfs(e[i].to,x); } vis[x]=0; return x; } void modify(int x,LL c) { int k=x,cnt=0; sv[x]+=c; for(;fa[k];k=fa[k]) { ++cnt; LL s=dtf[x][cnt]; sv[fa[k]]+=c; dsv[fa[k]]+=s*c; sva[k]+=c; dsva[k]+=s*c; } } LL calc(int x) { int k=x,cnt=0; LL res=dsv[x]; for(;fa[k];k=fa[k]) { ++cnt; LL s=dtf[x][cnt]; res+=dsv[fa[k]]-dsva[k]; res+=(sv[fa[k]]-sva[k])*s; } return res; } LL query(int x) { LL cs=calc(x); for(int i=hd[x];i!=-1;i=lk[i].next) { LL tmp=calc(lk[i].adj); if(tmp<cs) return query(lk[i].to); } return cs; } int main() { memset(vis,0,sizeof(vis)); memset(fr,-1,sizeof(fr)); memset(hd,-1,sizeof(hd)); int q; read(n);read(q); REP(i,1,n-1) { int u,v;LL d; read(u);read(v);read(d); addedge(u,v,d); } totsiz=n; int r=tdc(1,0); REP(i,1,q) { int u,e; read(u);read(e); modify(u,e); printf("%lld\n",query(r)); } return 0; } |