fork(1) download
copy 
  1. // this is TooDifficult's solution
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <string>
  8. #include <map>
  9. #include <set>
  10. #include <cassert>
  11. using namespace std;
  12. #define rep(i,a,n) for (int i=a;i<n;i++)
  13. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  14. #define pb push_back
  15. #define mp make_pair
  16. #define all(x) (x).begin(),(x).end()
  17. #define fi first
  18. #define se second
  19. #define SZ(x) ((int)(x).size())
  20. typedef vector<int> VI;
  21. typedef long long ll;
  22. typedef pair<int,int> PII;
  23. const ll mod=1000000007;
  24. const ll inf=1ll<<60;
  25. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  26. // head
  27.  
  28. const int N=201000;
  29. int q[N],hs[N],hv[N],dep[N],id[N],l[N],r[N],bel[N],s[N],f[N],pos[N],vl[N];
  30. int n,m,Q,tot,u,v,k,ty;
  31. VI e[N],vec[N],ret;
  32. pair<ll,int> ind[N],z;
  33. struct node {
  34. 	ll fg;
  35. 	pair<ll,int> s;
  36. }nd[4*N];
  37. void upd(int p) {
  38. 	nd[p].s=min(nd[p+p].s,nd[p+p+1].s);
  39. }
  40. void setf(int p,ll v) {
  41. 	nd[p].fg+=v; nd[p].s.fi+=v;
  42. }
  43. void build(int p,int l,int r) {
  44. 	nd[p].fg=0;
  45. 	if (l==r) {
  46. 		nd[p].s=ind[l];
  47. 	} else {
  48. 		int md=(l+r)>>1;
  49. 		build(p+p,l,md);
  50. 		build(p+p+1,md+1,r);
  51. 		upd(p);
  52. 	}
  53. }
  54. void push(int p) {
  55. 	if (nd[p].fg) {
  56. 		setf(p+p,nd[p].fg);
  57. 		setf(p+p+1,nd[p].fg);
  58. 		nd[p].fg=0;
  59. 	}
  60. }
  61. pair<ll,int> query(int p,int l,int r,int tl,int tr) {
  62. 	if (tl==l&&tr==r) return nd[p].s;
  63. 	else {
  64. 		push(p);
  65. 		int md=(l+r)>>1;
  66. 		if (tr<=md) return query(p+p,l,md,tl,tr);
  67. 		else if (tl>md) return query(p+p+1,md+1,r,tl,tr);
  68. 		else return min(query(p+p,l,md,tl,md),query(p+p+1,md+1,r,md+1,tr));
  69. 	}
  70. }
  71. void modify(int p,int l,int r,int tl,int tr,ll v) {
  72. 	if (tl>tr) return;
  73. 	if (tl==l&&tr==r) return setf(p,v);
  74. 	else {
  75. 		push(p);
  76. 		int md=(l+r)>>1;
  77. 		if (tr<=md) modify(p+p,l,md,tl,tr,v);
  78. 		else if (tl>md) modify(p+p+1,md+1,r,tl,tr,v);
  79. 		else modify(p+p,l,md,tl,md,v),modify(p+p+1,md+1,r,md+1,tr,v);
  80. 		upd(p);
  81. 	}
  82. }
  83.  
  84. void dfs(int u,int f) {
  85. 	id[l[u]=++tot]=u; ind[tot]=mp(inf,0);
  86. 	for (auto v:vec[u]) {
  87. 		ind[++tot]=mp(v,v);
  88. 		pos[v]=tot;
  89. 	}
  90. 	vl[u]=tot;
  91. 	dep[u]=dep[f]+1;
  92. 	if (hv[u]) dfs(hv[u],u);
  93. 	rep(j,0,SZ(e[u])) if (e[u][j]!=f&&e[u][j]!=hv[u])
  94. 		dfs(e[u][j],u);
  95. 	r[u]=tot;
  96. }
  97. void HLDoT(int rt) {
  98. 	int t=1;
  99. 	q[0]=rt;
  100. 	rep(i,0,n) {
  101. 		int u=q[i];
  102. 		rep(j,0,SZ(e[u])) if (e[u][j]!=f[u])
  103. 			f[e[u][j]]=u,dep[q[t++]=e[u][j]]=dep[u]+1;
  104. 	}
  105. 	per(i,0,n) {
  106. 		int u=q[i],p=f[u];
  107. 		s[u]++,s[p]+=s[u];
  108. 		if (!l[u]) l[u]=1;
  109. 		if (hs[p]<s[u]) hs[p]=s[u],hv[p]=u,l[p]=l[u]+1;
  110. 	}
  111. 	rep(i,0,n) {
  112. 		int u=q[i];
  113. 		if (!bel[u]) bel[u]=u;
  114. 		if (hv[u]) bel[hv[u]]=bel[u];
  115. 	}
  116. 	dfs(rt,0);
  117. }
  118. void query(int u,int v) {
  119. 	while (1) {
  120. 		if (bel[u]==bel[v]) {
  121. 			if (dep[u]<dep[v]) swap(u,v);
  122. 			z=min(z,query(1,1,m,l[v],vl[u]));
  123. 			break;
  124. 		} else {
  125. 			if (dep[bel[u]]<dep[bel[v]]) swap(u,v);
  126. 			z=min(z,query(1,1,m,l[bel[u]],vl[u]));
  127. 			u=f[bel[u]];
  128. 		}
  129. 	}
  130. }
  131.  
  132. int main() {
  133. 	scanf("%d%d%d",&n,&m,&Q);
  134. 	rep(i,1,n) {
  135. 		scanf("%d%d",&u,&v);
  136. 		e[u].pb(v); e[v].pb(u);
  137. 	}
  138. 	rep(i,0,m) {
  139. 		scanf("%d",&u);
  140. 		vec[u].pb(i+1);
  141. 	}
  142. 	HLDoT(1);
  143. 	m=tot;
  144. 	build(1,1,m);
  145. 	rep(i,0,Q) {
  146. 		scanf("%d",&ty);
  147. 		if (ty==1) {
  148. 			scanf("%d%d%d",&u,&v,&k);
  149. 			ret.clear();
  150. 			while (k>0) {
  151. 				z=mp(inf,0);
  152. 				query(u,v);
  153. 				if (z.fi>=1ll<<50) break;
  154. 				--k;
  155. 				ret.pb(z.se);
  156. 				modify(1,1,m,pos[z.se],pos[z.se],inf);
  157. 			}
  158. 			printf("%d",SZ(ret));
  159. 			for (auto u:ret) printf(" %d",u);
  160. 			puts("");
  161. 		} else {
  162. 			scanf("%d%d",&u,&k);
  163. 			modify(1,1,m,l[u],r[u],k);
  164. 		}
  165. 	}
  166. }
Success #stdin #stdout 0s 35664KB
comments (?)
stdin
copy 
4 6 4
1 2
1 3
1 4
3 1 4 2 1 1 
2 2 2
1 3 1 3
1 2 1 1
1 2 1 1
stdout
copy 
3 1 2 5
1 4
1 6
https://ideone.com/8fPh1i
language:
C++14 (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!