前排膜拜大佬 11Demensions
放代码
|
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 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 100010 struct Tedge { int to,val,ctr; Tedge() {} Tedge(int _,int __) { to=_; val=__; } }edge[N<<1]; #define TO edge[i].to #define VAL edge[i].val #define NXT nxt[i] int nxt[N<<1],fst[N],e_tot; void add_e(int _,int __,int val) { static int &i=e_tot; edge[i]=Tedge(_,val); nxt[i]=fst[__]; fst[__]=i++; edge[i]=Tedge(__,val); nxt[i]=fst[_]; fst[_]=i++; } bool use[N]; int siz[N],fa[N],dep[N],hs,lx=1,root,n,m; ll d[20][N],da[N],dm[N],c[N]; void g_siz(int x,int p) { siz[x]=1; for(int i=fst[x];~i;i=nxt[i]) if(!use[TO]&&TO!=p) g_siz(TO,x),siz[x]+=siz[TO]; return; } int gctr(int x,int p) { for(int i=fst[x];~i;i=NXT) if(!use[TO]&&siz[TO]>hs&&TO!=p) return gctr(TO,x); return x; } void calc_d(int x,int p) { for(int i=fst[x];~i;i=NXT) if(TO!=p&&!use[TO]) d[lx][TO]=d[lx][x]+VAL,calc_d(TO,x); } int build(int x) { int ctr; g_siz(x,0); hs=siz[x]/2; ctr=gctr(x,0); use[ctr]=true; dep[ctr]=lx; calc_d(ctr,0); lx++; for(int i=fst[ctr];~i;i=nxt[i]) if(!use[TO]) fa[edge[i].ctr=build(TO)]=ctr; lx--; return ctr; } void update(int x,int e) { for(int p=x;p;p=fa[p]) da[p]+=d[dep[p]][x]*e,dm[p]+=d[dep[p]-1][x]*e,c[p]+=e; } ll calc(int x) { static ll ret; ret=0; for(int p=x;p;p=fa[p]) ret+=da[p]-dm[p]+(d[dep[p]][x]-d[dep[p]-1][x])*c[p]; return ret; } ll solve(int x) { ll ans=calc(x); for(int i=fst[x],to;~i;i=nxt[i]) { to=TO; if(dep[to]>dep[x]&&calc(to)<calc(x)) return solve(edge[i].ctr); } return ans; } int main() { freopen("BZOJ3924.in","r",stdin); int u,v,val,e; memset(fst,-1,sizeof(fst)); read(n); read(m); For(i,1,n-1) { read(u); read(v); read(val); add_e(u,v,val); } root=build(1); for(;m;m--) { read(u); read(e); update(u,e); printf("%lld\n",solve(root)); } return 0; } |