Time Limit:?100 Sec??Memory Limit:?256 MB
Submit:?817??Solved:?376

Description

?傲嬌少女幽香正在玩一個非常有趣的戰略類游戲，本來這個游戲的地圖其實還不算太大，幽香還能管得過來，但是不知道為什么現在的網游廠商把游戲的地圖越做越大，以至于幽香一眼根本看不過來，更別說和別人打仗了。?在打仗之前，幽香現在面臨一個非常基本的管理問題需要解決。?整個地圖是一個樹結構，一共有n塊空地，這些空地被n-1條帶權邊連接起來，使得每兩個點之間有一條唯一的路徑將它們連接起來。在游戲中，幽香可能在空地上增加或者減少一些軍隊。同時，幽香可以在一個空地上放置一個補給站。?如果補給站在點u上，并且空地v上有dv個單位的軍隊，那么幽香每天就要花費dv×dist(u,v)的金錢來補給這些軍隊。由于幽香需要補給所有的軍隊，因此幽香總共就要花費為Sigma(Dv*dist(u，v),其中1<=V<=N)的代價。其中dist(u,v)表示u個v在樹上的距離（唯一路徑的權和）。?因為游戲的規定，幽香只能選擇一個空地作為補給站。在游戲的過程中，幽香可能會在某些空地上制造一些軍隊，也可能會減少某些空地上的軍隊，進行了這樣的操作以后，出于經濟上的考慮，幽香往往可以移動他的補給站從而省一些錢。但是由于這個游戲的地圖是在太大了，幽香無法輕易的進行最優的安排，你能幫幫她嗎？?你可以假定一開始所有空地上都沒有軍隊。?

Input

第一行兩個數n和Q分別表示樹的點數和幽香操作的個數，其中點從1到n標號。?接下來n-1行，每行三個正整數a,b,c，表示a和b之間有一條邊權為c的邊。?接下來Q行，每行兩個數u,e，表示幽香在點u上放了e單位個軍隊（如果e<0，就相當于是幽香在u上減少了|e|單位個軍隊，說白了就是du←du+e）。數據保證任何時刻每個點上的軍隊數量都是非負的。?

Output

?對于幽香的每個操作，輸出操作完成以后，每天的最小花費，也即如果幽香選擇最優的補給點進行補給時的花費。?

Sample Input

10 5
1 2 1
2 3 1
2 4 1
1 5 1
2 61
2 7 1
5 8 1
7 91
1 10 1
3 1
2 1
8 1
3 1
4 1

Sample Output

0
1
4
5
6

HINT

?

對于所有數據，1<=c<=1000, 0<=|e|<=1000, n<=105, Q<=105

?

Source

?

樹 動態樹分治

詢問樹的加權重心

可以發現這么一個性質：隨便選一個點，如果加權重心不在當前點，那么從當前點往加權重心走，花費肯定單調減小。

從上次的答案開始走，用動態點分治維護和查詢將當前點作為補給站的花費，然后暴力枚舉走向哪個方向

?

qsum里i少減了一個1，調了倆小時

?

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std; 10 const int INF=0x3f3f3f3f; 11 const int mxn=120010; 12 int read(){ 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 //inline int max(int a,int b){return a>b?a:b;} 19 //inline LL max(LL a,LL b){return a>b?a:b;} 20 //inline int min(int a,int b){return a<b?a:b;} 21 //inline LL min(LL a,LL b){return a<b?a:b;} 22 struct edge{ 23 int v,nxt,w; 24 }e[mxn<<1]; 25 int hd[mxn],mct=0; 26 void add_edge(int u,int v,int w){ 27 e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=w;hd[u]=mct;return; 28 } 29 int sz[mxn],mc[mxn],rt=0,smm; 30 //int f[mxn][20]; 31 bool vis[mxn]; 32 void DFS_sz(int u,int fa){ 33 sz[u]=1;mc[u]=0; 34 for(int i=hd[u],v;i;i=e[i].nxt){ 35 v=e[i].v; 36 if(v==fa || vis[v])continue; 37 DFS_sz(v,u); 38 sz[u]+=sz[v]; 39 mc[u]=max(mc[u],sz[v]); 40 } 41 mc[u]=max(mc[u],smm-sz[u]); 42 if(mc[u]<=mc[rt])rt=u; 43 return; 44 } 45 int dis[mxn][20],act[mxn]; 46 int g[mxn][20];//ansi 47 LL cost1[mxn],cost2[mxn]; 48 int num1[mxn],num2[mxn]; 49 // 50 void getship(int x,int fa,int an,int dist){ 51 // printf("x:%d fa:%d an:%d dist:%d\n",x,fa,an,dist); 52 for(int i=hd[x];i;i=e[i].nxt){ 53 int v=e[i].v; 54 if(v==fa || vis[v])continue; 55 g[v][++act[v]]=an;//新一級祖先 56 dis[v][act[v]]=dist+e[i].w;//距離 57 getship(v,x,an,dist+e[i].w); 58 } 59 return; 60 } 61 // 62 LL nowans=0;int nowpos=0; 63 int a[mxn];//軍隊人數 64 // 65 void solve(int x){ 66 // printf("solve:%d\n",x); 67 vis[x]=1; 68 getship(x,0,x,0); 69 g[x][++act[x]]=x; 70 for(int i=hd[x];i;i=e[i].nxt){ 71 int v=e[i].v; 72 if(vis[v])continue; 73 smm=sz[v]; 74 rt=0; 75 DFS_sz(v,x); 76 solve(rt); 77 } 78 return; 79 } 80 void update(int u,int E){ 81 num1[u]+=E; 82 for(int i=act[u];i>1;i--){ 83 // int dist=dis[g[u][i]][act[g[u][i]]-1]; 84 int dist=dis[u][i-1]; 85 cost2[g[u][i]]+=(LL)dist*E; 86 cost1[g[u][i-1]]+=(LL)dist*E; 87 num2[g[u][i]]+=E; 88 num1[g[u][i-1]]+=E; 89 } 90 return; 91 } 92 LL qsum(int x){ 93 // printf("Qsum:%d \n",x); 94 LL res=cost1[x]; 95 for(int i=act[x];i>1;i--){ 96 LL dist=dis[x][i-1]; 97 res+=cost1[g[x][i-1]]-cost2[g[x][i]]; 98 res+=(LL)dist*(num1[g[x][i-1]]-num2[g[x][i]]); 99 } 100 return res; 101 } 102 void Move(int x,int from){ 103 // printf("move:%d\n",x); 104 for(int i=hd[x];i;i=e[i].nxt){ 105 int v=e[i].v; 106 if(v==from)continue; 107 LL co=qsum(v); 108 if(co<nowans){ 109 nowans=co; 110 nowpos=v; 111 Move(v,x); 112 break; 113 } 114 } 115 return; 116 } 117 int n,Q; 118 int main(){ 119 // freopen("in.txt","r",stdin); 120 // freopen("zjoi15_tree1.in","r",stdin); 121 // freopen("zjoi15_tree1.out","w",stdout); 122 int i,j; 123 n=read();Q=read(); 124 int a,b,c,u,e; 125 for(i=1;i<n;i++){ 126 a=read();b=read();c=read(); 127 add_edge(a,b,c); 128 add_edge(b,a,c); 129 } 130 mc[rt=0]=INF; 131 smm=n; 132 DFS_sz(1,0); 133 int rot=rt; 134 solve(rt); 135 nowpos=rot; 136 while(Q--){ 137 u=read();e=read(); 138 update(u,e); 139 nowans=qsum(nowpos); 140 Move(nowpos,0); 141 printf("%lld\n",nowans); 142 } 143 return 0; 144 }

?

?

Time Limit:?100 Sec??Memory Limit:?256 MB
Submit:?817??Solved:?376
[Submit][Status][Discuss]

Description

?傲嬌少女幽香正在玩一個非常有趣的戰略類游戲，本來這個游戲的地圖其實還不算太大，幽香還能管得過來，但是不知道為什么現在的網游廠商把游戲的地圖越做越大，以至于幽香一眼根本看不過來，更別說和別人打仗了。?在打仗之前，幽香現在面臨一個非常基本的管理問題需要解決。?整個地圖是一個樹結構，一共有n塊空地，這些空地被n-1條帶權邊連接起來，使得每兩個點之間有一條唯一的路徑將它們連接起來。在游戲中，幽香可能在空地上增加或者減少一些軍隊。同時，幽香可以在一個空地上放置一個補給站。?如果補給站在點u上，并且空地v上有dv個單位的軍隊，那么幽香每天就要花費dv×dist(u,v)的金錢來補給這些軍隊。由于幽香需要補給所有的軍隊，因此幽香總共就要花費為Sigma(Dv*dist(u，v),其中1<=V<=N)的代價。其中dist(u,v)表示u個v在樹上的距離（唯一路徑的權和）。?因為游戲的規定，幽香只能選擇一個空地作為補給站。在游戲的過程中，幽香可能會在某些空地上制造一些軍隊，也可能會減少某些空地上的軍隊，進行了這樣的操作以后，出于經濟上的考慮，幽香往往可以移動他的補給站從而省一些錢。但是由于這個游戲的地圖是在太大了，幽香無法輕易的進行最優的安排，你能幫幫她嗎？?你可以假定一開始所有空地上都沒有軍隊。?

Input

第一行兩個數n和Q分別表示樹的點數和幽香操作的個數，其中點從1到n標號。?接下來n-1行，每行三個正整數a,b,c，表示a和b之間有一條邊權為c的邊。?接下來Q行，每行兩個數u,e，表示幽香在點u上放了e單位個軍隊（如果e<0，就相當于是幽香在u上減少了|e|單位個軍隊，說白了就是du←du+e）。數據保證任何時刻每個點上的軍隊數量都是非負的。?

Output

?對于幽香的每個操作，輸出操作完成以后，每天的最小花費，也即如果幽香選擇最優的補給點進行補給時的花費。?

Sample Input

10 5
1 2 1
2 3 1
2 4 1
1 5 1
2 61
2 7 1
5 8 1
7 91
1 10 1
3 1
2 1
8 1
3 1
4 1

Sample Output

0
1
4
5
6

HINT

?

對于所有數據，1<=c<=1000, 0<=|e|<=1000, n<=105, Q<=105

?

Source

轉載于:https://www.cnblogs.com/SilverNebula/p/6723342.html

總結

以上是生活随笔為你收集整理的Bzoj3924 [Zjoi2015]幻想乡战略游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。