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.  
  117. inline void maintain(int p){
  118. 	t[p].sz=t[t[p].c[0]].sz+t[t[p].c[1]].sz+1;
  119. 	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));
  120. 	t[p].sum=t[t[p].c[0]].sum+t[t[p].c[1]].sum+t[p].val;
  121. 	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));
  122. 	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);
  123. }
  124.  
  125. inline void pushdown(int p){
  126. 	if (t[p].rev)
  127. 	{
  128. 		swap(t[p].c[0],t[p].c[1]);
  129. 		swap(t[p].lm,t[p].rm);
  130. 		if (t[p].c[0]) t[t[p].c[0]].rev^=1;
  131. 		if (t[p].c[1]) t[t[p].c[1]].rev^=1;
  132. 		//update_rev(t[p].c[0]);
  133. 		//update_rev(t[p].c[1]);
  134. 		t[p].rev=false;
  135. 	}
  136.  
  137. 	if (t[p].ocr!=inf)
  138. 	{
  139. 		if (t[p].c[0])
  140. 			occur(t[p].c[0],t[p].ocr);
  141. 		if (t[p].c[1])
  142. 			occur(t[p].c[1],t[p].ocr);
  143. 		t[p].ocr=inf;
  144. 	}
  145. }
  146.  
  147. inline void setc(const int &p,const int &x,const int &kd){
  148. 	if (p) t[p].c[kd]=x;
  149. 	if (x) t[x].fa=p;
  150. }
  151.  
  152. void rotate(int x){
  153. 	if (!t[x].fa) return ;
  154. 	int p=t[x].fa;
  155. 	pushdown(p);
  156. 	pushdown(x);
  157.  
  158. 	int mark=t[p].c[1]==x;
  159.  
  160. 	if (t[p].rt)
  161. 	{
  162. 		t[p].rt=false;
  163. 		t[x].rt=true;
  164. 		t[x].fa=t[p].fa;
  165. 	}
  166. 	else
  167. 		setc(t[p].fa,x,t[t[p].fa].c[1]==p);
  168. 	setc(p,t[x].c[mark^1],mark);
  169. 	setc(x,p,mark^1);
  170.  
  171. 	maintain(p);
  172. 	maintain(x);
  173. }
  174.  
  175. void splay(int x){
  176. 	pushdown(x);
  177. 	while (!t[x].rt)
  178. 	{
  179. 		if (t[t[x].fa].rt)
  180. 		{
  181. 			rotate(x);
  182. 			break;
  183. 		}
  184. 		if ((t[t[t[x].fa].fa].c[0]==t[x].fa)==(t[t[x].fa].c[0]==x))
  185. 			rotate(t[x].fa);
  186. 		else
  187. 			rotate(x);
  188. 		rotate(x);
  189. 	}
  190. }
  191.  
  192. int expose(int x){
  193. 	int y=0;
  194. 	do
  195. 	{
  196. 		splay(x);
  197. 		t[t[x].c[1]].rt=true;
  198. 		t[x].c[1]=y;
  199. 		t[y].rt=false;
  200. 		maintain(x);
  201. 		x=t[y=x].fa;
  202. 	}while(x);
  203. 	return y;
  204. }
  205.  
  206. int mroot(int x){
  207. 	expose(x);
  208. 	splay(x);
  209. 	t[x].rev^=1;
  210. 	//update_rev(x);
  211. }
  212.  
  213. void init()
  214. {
  215. 	RI(n);
  216. 	int x,y;
  217. 	REP(i,1,n) RI(x),t[i]=lct(x);
  218. 	REP(i,2,n) RII(x,y),add(x,y),add(y,x);
  219. }
  220.  
  221. void dfs(int p,int fa=0){
  222. 	for (int i=hd[p];i;i=nxt[i])
  223. 	if (to[i]!=fa)
  224. 	{
  225. 		t[to[i]].fa=p;
  226. 		dfs(to[i],p);
  227. 	}
  228. }
  229.  
  230. void work(){
  231. 	int _=0;
  232. 	RI(_);
  233. 	int op;
  234. 	int a,b,c;
  235. 	int now;
  236. 	REP(__,1,_)
  237. 	{
  238. 		RI(op);
  239. 		RII(a,b);
  240. 		mroot(a);
  241. 		now=expose(b);
  242. 		if (op&1)
  243. 			printf("%d\n",max(t[now].mx,0));
  244. 		else
  245. 		{
  246. 			RI(c);
  247. 			occur(now,c);
  248. 		}
  249. 	}
  250. }
  251.  
  252. int main()
  253. {
  254. 	//open();
  255. 	int _=0;
  256. 	init();
  257. 	dfs(1);
  258. 	work();
  259. 	close();
  260. 	return 0;
  261. }
  262.  
  263.  
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/xDXzIS
WA,problem GSS7, based on SPOJ submission 16329982 (C++ 5), 2016-02-21 10:06:27
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!