fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <string>
  5. #include <cstring>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <algorithm>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <vector>
  13.  
  14. #define REP(I,A,B) for(int I=A,_END_=B;I<=_END_;I++)
  15. #define REPD(I,A,B) for(int I=A,_END_=B;I>=_END_;I--)
  16. #define RI(X) X=Readint()
  17. #define RII(X,Y) RI(X),RI(Y)
  18. #define RIII(X,Y,Z) RI(X),RI(Y),RI(Z)
  19. #define RS(X) scanf("%s",X)
  20. #define RD(X) scanf("%lf",&X)
  21. #define GCH getchar()
  22. #define PCH(X) putchar(X)
  23. #define MS(X,Y) memset(X,Y,sizeof(X))
  24. #define MC(X,Y,var,len) memcpy(X,Y,sizeof(var)*(len))
  25. #define debug(...) fprintf(stderr,__VA_ARGS__)
  26. #define pb(X) push_back(X)
  27. #define mp(A,B) make_pair(A,B)
  28. #define fr first
  29. #define sc second
  30. #define lch(p) (p+p)
  31. #define rch(p) (p+p+1)
  32. #define lowbit(X) ((X)&(-(X)))
  33.  
  34. using namespace std;
  35.  
  36. typedef pair<int,int> poi;
  37.  
  38. inline int Readint()
  39. {
  40. 	int ret=0;
  41. 	int f=1;
  42. 	char ch;
  43. 	do
  44. 	{
  45. 		ch=GCH;
  46. 		if (ch=='-') f*=-1;
  47. 	}while(ch>=0 && (ch<'0' || ch>'9'));
  48.  
  49. 	while ('0'<=ch && ch<='9')
  50. 	{
  51. 		ret=ret*10+ch-'0';
  52. 		ch=GCH;
  53. 	}
  54. 	return ret*f;
  55. }
  56.  
  57. void open()
  58. {
  59. 	freopen("GSS7.in","r",stdin);
  60. 	freopen("GSS7.out","w",stdout);
  61. }
  62. void close()
  63. {
  64. 	fclose(stdin);
  65. 	fclose(stdout);
  66. }
  67.  
  68. const int MAXN = 101010;
  69. const int inf = 11111;
  70.  
  71. int tot;
  72. int to[MAXN*2]={0};
  73. int nxt[MAXN*2]={0};
  74. int hd[MAXN];
  75.  
  76. int n;
  77.  
  78. inline void add(const int &x,const int &y){
  79. 	tot++;
  80. 	to[tot]=y;
  81. 	nxt[tot]=hd[x];
  82. 	hd[x]=tot;
  83. }
  84.  
  85. struct lct{
  86. 	bool rev;
  87. 	bool rt;
  88. 	int sz;
  89. 	int sum,mx,lm,rm,val,ocr;
  90. 	int c[2];
  91. 	int fa;
  92. 	lct(){}
  93. 	lct(int vl){
  94. 		c[0]=c[1]=fa=0;
  95. 		ocr=inf;
  96. 		rt=true;
  97. 		rev=false;
  98. 		sum=mx=lm=rm=vl;
  99. 		val=vl;
  100. 		sz=1;
  101. 	}
  102. }t[MAXN];
  103.  
  104. inline void occur(const int &p,int c){
  105. 	t[p].sum=t[p].lm=t[p].rm=t[p].mx=c*t[p].sz;
  106. 	t[p].ocr=t[p].val=c;
  107. }
  108.  
  109. inline void update_rev(int p){
  110. 	if (!p) return ;
  111. 	swap(t[p].c[0],t[p].c[1]);
  112. 	swap(t[p].lm,t[p].rm);
  113. 	t[p].rev^=1;
  114. }
  115.  
  116. inline void maintain(int p){
  117. 	t[p].sz=t[t[p].c[0]].sz+t[t[p].c[1]].sz+1;
  118. 	t[p].mx=max(max(t[t[p].c[0]].rm,0)+t[p].val+max(t[t[p].c[1]].lm,0),max(t[t[p].c[0]].mx,t[t[p].c[1]].mx));
  119. 	t[p].sum=t[t[p].c[0]].sum+t[t[p].c[1]].sum+t[p].val;
  120. 	t[p].lm=max(t[t[p].c[0]].lm,t[t[p].c[0]].sum+t[p].val+max(t[t[p].c[1]].lm,0));
  121. 	t[p].rm=max(max(t[t[p].c[0]].rm,0)+t[p].val+t[t[p].c[1]].sum,t[t[p].c[1]].rm);
  122. }
  123.  
  124. inline void pushdown(int p){
  125. 	if (t[p].rev)
  126. 	{
  127. 		update_rev(t[p].c[0]);
  128. 		update_rev(t[p].c[1]);
  129. 		t[p].rev=false;
  130. 	}
  131.  
  132. 	if (t[p].ocr!=inf)
  133. 	{
  134. 		if (t[p].c[0])
  135. 			occur(t[p].c[0],t[p].ocr);
  136. 		if (t[p].c[1])
  137. 			occur(t[p].c[1],t[p].ocr);
  138. 		t[p].ocr=inf;
  139. 	}
  140. }
  141.  
  142. inline void setc(const int &p,const int &x,const int &kd){
  143. 	if (p) t[p].c[kd]=x;
  144. 	if (x) t[x].fa=p;
  145. }
  146.  
  147. void rotate(int x){
  148. 	if (!t[x].fa) return ;
  149. 	int p=t[x].fa;
  150. 	pushdown(p);
  151. 	pushdown(x);
  152.  
  153. 	int mark=t[p].c[1]==x;
  154.  
  155. 	if (t[p].rt)
  156. 	{
  157. 		t[p].rt=false;
  158. 		t[x].rt=true;
  159. 		t[x].fa=t[p].fa;
  160. 	}
  161. 	else
  162. 		setc(t[p].fa,x,t[t[p].fa].c[1]==p);
  163. 	setc(p,t[x].c[mark^1],mark);
  164. 	setc(x,p,mark^1);
  165.  
  166. 	maintain(p);
  167. 	maintain(x);
  168. }
  169.  
  170. void splay(int x){
  171. 	pushdown(x);
  172. 	while (!t[x].rt)
  173. 	{
  174. 		if (t[t[x].fa].rt)
  175. 		{
  176. 			rotate(x);
  177. 			break;
  178. 		}
  179. 		if ((t[t[t[x].fa].fa].c[0]==t[x].fa)==(t[t[x].fa].c[0]==x))
  180. 			rotate(t[x].fa);
  181. 		else
  182. 			rotate(x);
  183. 		rotate(x);
  184. 	}
  185. }
  186.  
  187. int expose(int x){
  188. 	int y=0;
  189. 	do
  190. 	{
  191. 		splay(x);
  192. 		t[t[x].c[1]].rt=true;
  193. 		t[x].c[1]=y;
  194. 		t[y].rt=false;
  195. 		maintain(x);
  196. 		x=t[y=x].fa;
  197. 	}while(x);
  198. 	return y;
  199. }
  200.  
  201. int mroot(int x){
  202. 	expose(x);
  203. 	splay(x);
  204. 	update_rev(x);
  205. }
  206.  
  207. void init()
  208. {
  209. 	RI(n);
  210. 	int x,y;
  211. 	REP(i,1,n) RI(x),t[i]=lct(x);
  212. 	REP(i,2,n) RII(x,y),add(x,y),add(y,x);
  213. }
  214.  
  215. void dfs(int p,int fa=0){
  216. 	for (int i=hd[p];i;i=nxt[i])
  217. 	if (to[i]!=fa)
  218. 	{
  219. 		t[to[i]].fa=p;
  220. 		dfs(to[i],p);
  221. 	}
  222. }
  223.  
  224. void work(){
  225. 	int _=0;
  226. 	RI(_);
  227. 	int op;
  228. 	int a,b,c;
  229. 	int now;
  230. 	REP(__,1,_)
  231. 	{
  232. 		RI(op);
  233. 		RII(a,b);
  234. 		mroot(a);
  235. 		now=expose(b);
  236. 		if (op&1)
  237. 			printf("%d\n",max(t[now].mx,0));
  238. 		else
  239. 		{
  240. 			RI(c);
  241. 			occur(now,c);
  242. 		}
  243. 	}
  244. }
  245.  
  246. int main()
  247. {
  248. 	//open();
  249. 	int _=0;
  250. 	init();
  251. 	dfs(1);
  252. 	work();
  253. 	close();
  254. 	return 0;
  255. }
  256.  
  257.  
Success #stdin #stdout 0s 9768KB
comments (?)
stdin
copy 
5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5
stdout
copy 
5
9
https://ideone.com/7VkM6Q
AC，problem GSS7, based on SPOJ submission 16328469 (C 5), 2016-02-21 02:35:25
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!