【BZOJ5129】【Lydsy1712月赛】树上传送

Author Avatar
q234rty 4月 03, 2018

点分治+最短路即可。

首先看到距离不超过某个数的限制可以想到点分治。

我们建出原树的点分树，对于每个根我们bfs一遍，得到它子树中的节点到根的距离以及按到根的距离排序后的序列。

考虑Dijkstra算法，传统的Dijkstra中每个点可能被松弛成功多次，但是这题每个点所有出边的权值都是相同的，我们每次取 w_i=dis_i+cost_i 最小的点出来松弛，就可以保证每个点第一次被松弛成功就是最优的，于是我们可以将这个点删去。

这样我们每次拿出来 w_i 最小的点 u ，枚举其和要松弛的点的 lca ，将其子树中的点按照距离从小到大松弛就可以了。具体实现时类似当前弧。

至于点分治的写法，安利11Dimensions的写法QwQ

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<ll,int> pli;
  5. const int MAXSIZE=10000020;
  6. int bufpos;
  7. char buf[MAXSIZE];
  8. #define NEG 0
  9. void init(){
  10. 	#ifdef LOCAL
  11. 		freopen("5129.txt","r",stdin);
  12. 		freopen("5129.out","w",stdout);
  13. 	#endif
  14. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  15. 	bufpos=0;
  16. }
  17. #if NEG
  18. int readint(){
  19. 	bool isneg;
  20. 	int val=0;
  21. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  22. 	bufpos+=(isneg=buf[bufpos]=='-');
  23. 	for(;isdigit(buf[bufpos]);bufpos++)
  24. 		val=val*10+buf[bufpos]-'0';
  25. 	return isneg?-val:val;
  26. }
  27. #else
  28. int readint(){
  29. 	int val=0;
  30. 	for(;!isdigit(buf[bufpos]);bufpos++);
  31. 	for(;isdigit(buf[bufpos]);bufpos++)
  32. 		val=val*10+buf[bufpos]-'0';
  33. 	return val;
  34. }
  35. #endif
  36. char readchar(){
  37. 	for(;isspace(buf[bufpos]);bufpos++);
  38. 	return buf[bufpos++];
  39. }
  40. int readstr(char* s){
  41. 	int cur=0;
  42. 	for(;isspace(buf[bufpos]);bufpos++);
  43. 	for(;!isspace(buf[bufpos]);bufpos++)
  44. 		s[cur++]=buf[bufpos];
  45. 	s[cur]='\0';
  46. 	return cur;
  47. }
  48. const int maxn=300002;
  49. const int maxm=600002;
  50. const int nlgn=maxn*20;
  51. struct graph{
  52. 	int n,m;
  53. 	struct edge{
  54. 		int to,next;
  55. 	}e[maxm];
  56. 	int first[maxn];
  57. 	void addedge(int from,int to){
  58. 		e[++m]=(edge){to,first[from]};
  59. 		first[from]=m;
  60. 	}
  61. 	int sz[maxn];
  62. 	bool vis[maxn];
  63. 	int d[maxn][21];
  64. 	int gs(int u,int fa){
  65. 		sz[u]=1;
  66. 		for(int i=first[u];i;i=e[i].next){
  67. 			int v=e[i].to;
  68. 			if (v!=fa && !vis[v])
  69. 				sz[u]+=gs(v,u);
  70. 		}
  71. 		return sz[u];
  72. 	}
  73. 	int h;
  74. 	int ctrd(int u,int fa){
  75. 		for(int i=first[u];i;i=e[i].next){
  76. 			int v=e[i].to;
  77. 			if (v!=fa && !vis[v] && sz[v]>h)
  78. 				return ctrd(v,u);
  79. 		}
  80. 		return u;
  81. 	}
  82. 	int qwq[nlgn];
  83. 	int st[maxn],en[maxn],cur;
  84. 	int dep[maxn];
  85. 	void bfs(int s,int ly){
  86. 		cur++;
  87. 		int l=cur,r=cur;
  88. 		qwq[cur]=s;
  89. 		d[s][ly]=0;
  90. 		while(l<=r){
  91. 			int u=qwq[l++];
  92. 			for(int i=first[u];i;i=e[i].next){
  93. 				int v=e[i].to;
  94. 				if (d[v][ly]!=-1 || vis[v])
  95. 					continue;
  96. 				d[v][ly]=d[u][ly]+1;
  97. 				qwq[++r]=v;
  98. 			}
  99. 		}
  100. 		cur=r;
  101. 	}
  102. 	int f[maxn];
  103. 	int dcomp(int u,int ly){
  104. 		h=gs(u,0)/2;
  105. 		int rt=ctrd(u,0);
  106. 		vis[rt]=1;
  107. 		st[rt]=cur+1;
  108. 		dep[rt]=ly;
  109. 		bfs(rt,ly);
  110. 		en[rt]=cur;
  111. 		for(int i=first[rt];i;i=e[i].next){
  112. 			int v=e[i].to;
  113. 			if (!vis[v])
  114. 				f[dcomp(v,ly+1)]=rt;
  115. 		}
  116. 		return rt;
  117. 	}
  118. 	priority_queue<pli,vector<pli>,greater<pli> > q;
  119. 	int lim[maxn],cost[maxn];
  120. 	ll w[maxn];
  121. 	void dijkstra(int s){
  122. 		memset(w,0x3f,(n+1)*8);
  123. 		w[s]=cost[s];
  124. 		q.push(make_pair(w[s],s));
  125. 		while(!q.empty()){
  126. 			pli p=q.top();
  127. 			q.pop();
  128. 			int u=p.second,tat=u;
  129. 			while(u){
  130. 				for(int& i=st[u];i<=en[u];i++){ //看起来很像当前弧？喵啊
  131. 					int v=qwq[i];
  132. 					int dis=d[tat][dep[u]]+d[v][dep[u]];
  133. 					if (dis>lim[tat])
  134. 						break;
  135. 					if (p.first+cost[v]<w[v]){
  136. 						w[v]=p.first+cost[v];
  137. 						q.push(make_pair(w[v],v));
  138. 					}
  139. 				}
  140. 				u=f[u];
  141. 			}
  142. 		}
  143. 	}
  144. 	void work(int s){
  145. 		memset(d,-1,sizeof(d));
  146. 		dcomp(1,0);
  147. 		dijkstra(s);
  148. 	}
  149. }g;
  150. int main(){
  151. 	init();
  152. 	int n=g.n=readint(),s=readint();
  153. 	for(int i=1;i<n;i++){
  154. 		int u=readint(),v=readint();
  155. 		g.addedge(u,v);
  156. 		g.addedge(v,u);
  157. 	}
  158. 	for(int i=1;i<=n;i++)	
  159. 		g.lim[i]=readint(),g.cost[i]=readint();
  160. 	g.work(s);
  161. 	for(int i=1;i<=n;i++)
  162. 		printf("%lld\n",g.w[i]-g.cost[i]);
  163. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/04/03/bzoj5129/

隐藏