Advertisement
Guest User

Untitled

a guest
Oct 25th, 2016
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.65 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MaxN=500010,inf=1000000000;
  7. struct edge
  8. {
  9. int nod,c;
  10. };
  11. vector<edge> v[MaxN];
  12. int special[MaxN],size[MaxN],niv[MaxN],centru;
  13. char vaz[MaxN],bun[MaxN];
  14.  
  15. void dfs1(int nod,int tata,int &n)
  16. {
  17. size[nod]=1;
  18. n++;
  19. for(vector<edge>::iterator it=v[nod].begin();it!=v[nod].end();it++)
  20. if(it->nod!=tata && !vaz[it->nod])
  21. {
  22. dfs1(it->nod,nod,n);
  23. size[nod]+=size[it->nod];
  24. }
  25. }
  26.  
  27. void get_center(int nod,int tata,int n)
  28. {
  29. int ok=1;
  30. for(vector<edge>::iterator it=v[nod].begin();it!=v[nod].end();it++)
  31. if(it->nod!=tata && !vaz[it->nod])
  32. {
  33. get_center(it->nod,nod,n);
  34. if(size[it->nod]>n/2+1) ok=0;
  35. }
  36. if(n-size[nod]>n/2+1) ok=0;
  37. if(ok) centru=nod;
  38. }
  39.  
  40. void dfs2(int nod,int tata,int res,int &res1)
  41. {
  42. if(res!=inf && niv[nod]!=res) bun[nod]=1;
  43. if(special[nod]>-1)
  44. if(res1==inf) res1=special[nod]-niv[nod];
  45. else if(res1!=special[nod]-niv[nod]) res1=-1;
  46. for(vector<edge>::iterator it=v[nod].begin();it!=v[nod].end();it++)
  47. if(it->nod!=tata && !vaz[it->nod])
  48. {
  49. niv[it->nod]=niv[nod]+it->c;
  50. dfs2(it->nod,nod,res,res1);
  51. }
  52. }
  53.  
  54. void solve(int nod)
  55. {
  56. int n=0;
  57. dfs1(nod,0,n);
  58. get_center(nod,0,n);
  59. int center=centru,res=inf;
  60. if(special[center]>-1) res=special[center];
  61. for(vector<edge>::iterator it=v[center].begin();it!=v[center].end();it++)
  62. if(!vaz[it->nod])
  63. {
  64. niv[it->nod]=it->c;
  65. dfs2(it->nod,center,res,res);
  66. }
  67. if(res!=inf && res!=0) bun[center]=1;
  68. res=inf;
  69. for(vector<edge>::reverse_iterator it=v[center].rbegin();it!=v[center].rend();it++)
  70. if(!vaz[it->nod])
  71. {
  72. niv[it->nod]=it->c;
  73. dfs2(it->nod,center,res,res);
  74. }
  75. vaz[center]=1;
  76. for(vector<edge>::iterator it=v[center].begin();it!=v[center].end();it++)
  77. if(!vaz[it->nod])
  78. solve(it->nod);
  79. }
  80.  
  81. int main()
  82. {
  83. //freopen("file.in", "r", stdin);
  84. //freopen("file.out", "w", stdout);
  85. int n,k,x,y,s,nr=0;
  86. scanf("%d%d",&n,&k);
  87. for(int i=1;i<n;i++)
  88. {
  89. scanf("%d%d%d",&x,&y,&s);
  90. v[x].push_back({y,s});
  91. v[y].push_back({x,s});
  92. }
  93. for(int i=1;i<=n;i++) special[i]=-1;
  94. for(int i=1;i<=k;i++)
  95. {
  96. scanf("%d%d",&x,&s);
  97. special[x]=s;
  98. }
  99. solve(1);
  100. for(int i=1;i<=n;i++)
  101. if(!bun[i]) nr++;
  102. printf("%d\n",nr);
  103. for(int i=1;i<=n;i++)
  104. if(!bun[i]) printf("%d ",i);
  105. return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement