fork download
  1. /*
  2.  * [Ctsc2010]珠宝商.cpp
  3.  *
  4.  * Created on: 2011-4-20
  5.  * Author: user
  6.  */
  7.  
  8. #include <cstdio>
  9. #include <iostream>
  10. #include <algorithm>
  11. #include <climits>
  12. #include <cstring>
  13. #include <vector>
  14. #include <cctype>
  15. #include <cassert>
  16. #include <map>
  17. #define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
  18. using namespace std;
  19. const int MAX_N_VERTEXS = 50000 + 10;
  20. const int MAX_L_PAT = 50000 + 10;
  21. const int MAX_LOG = 20;
  22. const int MAX_NLOGN = MAX_N_VERTEXS * MAX_LOG;
  23. const int MAX_N_ALPHA = 26;
  24.  
  25. int nVertexs;
  26. int patLen;
  27. char pat[MAX_L_PAT];
  28.  
  29. struct Vertex;
  30.  
  31. struct Edge {
  32. Edge*prev, *next, *op;
  33. Vertex*dst;
  34. void reSet() {
  35. prev->next = this;
  36. next->prev = this;
  37. }
  38. void erase() {
  39. prev->next = next;
  40. next->prev = prev;
  41. }
  42. Edge(Vertex*_dst, Edge*_prev, Edge*_next) :
  43. dst(_dst), prev(_prev), next(_next) {
  44. reSet();
  45. }
  46. Edge() {
  47. prev = next = 0;
  48. dst = 0;
  49. }
  50. };
  51.  
  52. struct Trie {
  53. Trie*ch[MAX_N_ALPHA];
  54.  
  55. Trie*fail;
  56. Trie() {
  57. memset(ch, 0, sizeof ch);
  58. }
  59.  
  60. int begin, end;
  61. int depth;
  62.  
  63. Trie*fail2k[MAX_LOG];
  64.  
  65. Trie*go(int what) {
  66. Trie*&c = ch[what];
  67. if (c == 0)
  68. c = new Trie;
  69. return c;
  70. }
  71. };
  72.  
  73. struct Vertex {
  74. Edge*begin, *end;
  75. char ch;
  76. Vertex*father;
  77.  
  78. int size;
  79.  
  80. Trie*where;
  81. int branch;
  82.  
  83. bool visited;
  84.  
  85. Vertex() {
  86. begin = new Edge;
  87. end = new Edge;
  88. begin->next = end;
  89. end->prev = begin;
  90. }
  91. };
  92.  
  93. Vertex vertexs[MAX_N_VERTEXS];
  94.  
  95. void addEdge(Vertex*u, Vertex*v) {
  96. Edge*uv = new Edge(v, u->begin, u->begin->next);
  97. Edge*vu = new Edge(u, v->begin, v->begin->next);
  98. uv->op = vu;
  99. vu->op = uv;
  100. }
  101.  
  102. void readInput() {
  103. scanf("%d%d", &nVertexs, &patLen);
  104. for (int i = 0; i < nVertexs - 1; ++i) {
  105. int a, b;
  106. scanf("%d%d", &a, &b);
  107. Vertex*u = vertexs + --a, *v = vertexs + --b;
  108. addEdge(u, v);
  109. }
  110.  
  111. for (int i = 0; i < nVertexs; ++i) {
  112. char ch;
  113. while (ch = getchar(), !isalpha(ch))
  114. ;
  115. vertexs[i].ch = ch;
  116. }
  117. scanf(" ");
  118. scanf("%s", pat);
  119. }
  120. int dfsCur;
  121.  
  122. void dfs(Trie* t, int _depth) {
  123. if (!t)
  124. return;
  125. t->depth = _depth;
  126. t->begin = dfsCur++;
  127. for (int i = 0; i < MAX_N_ALPHA; ++i) {
  128. dfs(t->ch[i], t->depth + 1);
  129. }
  130. t->end = dfsCur - 1;
  131. }
  132.  
  133. Vertex*que[MAX_N_VERTEXS];
  134. int qh, qt;
  135.  
  136. void doBFS(Vertex*root) {
  137. qh = qt = 0;
  138. que[qt++] = root;
  139. root->father = 0;
  140. for (; qh < qt;) {
  141. Vertex*u = que[qh++];
  142. for (Edge*e = u->begin->next; e != u->end; e = e->next) {
  143. Vertex*v = e->dst;
  144. if (v == u->father)
  145. continue;
  146. que[qt++] = v;
  147. v->father = u;
  148. }
  149. }
  150. }
  151.  
  152. Vertex* findSplitVertex(Vertex*root) {
  153. doBFS(root);
  154. for (int i = qt - 1; i >= 0; --i) {
  155. Vertex*u = que[i];
  156. u->size = 1;
  157. for (Edge*e = u->begin->next; e != u->end; e = e->next) {
  158. Vertex*v = e->dst;
  159. if (v == u->father)
  160. continue;
  161. u->size += v->size;
  162. }
  163. }
  164.  
  165. int bestOpt = INT_MAX;
  166. Vertex*best;
  167.  
  168. for (int i = 0; i < qt; ++i) {
  169. Vertex*u = que[i];
  170. int opt = root->size - u->size;
  171. for (Edge*e = u->begin->next; e != u->end; e = e->next) {
  172. Vertex*v = e->dst;
  173. if (v == u->father)
  174. continue;
  175. opt = max(opt, v->size);
  176. }
  177.  
  178. if (opt < bestOpt) {
  179. bestOpt = opt;
  180. best = u;
  181. }
  182. }
  183.  
  184. return best;
  185. }
  186.  
  187. const int MAX_N_SPLITS = MAX_N_VERTEXS * 2;
  188.  
  189. Trie*trieRoot = new Trie;
  190. struct Split {
  191. vector<Trie*>* trieByBranch;
  192. int nBranch;
  193.  
  194. void init(int nBranch) {
  195. trieByBranch = new vector<Trie*> [nBranch];
  196. this->nBranch = nBranch;
  197. }
  198.  
  199. void add(int branch, Trie*t) {
  200. trieByBranch[branch].push_back(t);
  201. }
  202. };
  203.  
  204. Split splits[MAX_N_SPLITS];
  205. int splitsCur = 0;
  206.  
  207. void buildSplit(Vertex*root, Split&split) {
  208. root->where = trieRoot->go(root->ch - 'a');
  209. doBFS(root);
  210.  
  211. int curBranch = 0;
  212. for (Edge*e = root->begin->next; e != root->end; e = e->next) {
  213. e->dst->branch = curBranch++;
  214. }
  215. root->branch = curBranch++;
  216. split.init(curBranch);
  217. for (int i = 1; i < qt; ++i) {
  218. Vertex*u = que[i];
  219. u->where = u->father->where->go(u->ch - 'a');
  220. if (u->father != root) {
  221. u->branch = u->father->branch;
  222. }
  223. }
  224. for (int i = 0; i < qt; ++i) {
  225. split.add(que[i]->branch, que[i]->where);
  226. }
  227. }
  228.  
  229. void doTreeSplit(Vertex*root) {
  230. int id = splitsCur++;
  231. root = findSplitVertex(root);
  232. buildSplit(root, splits[id]);
  233. for (Edge*e = root->begin->next; e != root->end; e = e->next) {
  234. e->erase();
  235. e->op->erase();
  236. doTreeSplit(e->dst);
  237. }
  238. }
  239.  
  240. void getDfsOrd() {
  241. dfsCur = 0;
  242. dfs(trieRoot, 0);
  243. }
  244.  
  245. struct Point {
  246. int x, y;
  247. int val;
  248.  
  249. Point() {
  250. val = 0;
  251. }
  252. Point(int _x, int _y) :
  253. x(_x), y(_y) {
  254. val = 0;
  255. }
  256.  
  257. bool operator<(const Point&p) const {
  258. return x < p.x;
  259. }
  260. };
  261.  
  262. bool cmpPointPtrByY(Point*a, Point*b) {
  263. return a->y < b->y;
  264. }
  265.  
  266. struct DataStruct {
  267. static const int MAX_N_POINTS = MAX_NLOGN;
  268. static const int MAX_SQRT_N_POINTS = 1000 + 10;
  269.  
  270. struct Block {
  271. int sum[MAX_SQRT_N_POINTS];
  272. Point*points[MAX_SQRT_N_POINTS];
  273.  
  274. int n;
  275. int addAll;
  276.  
  277. int L, R;
  278.  
  279. void set(int _L) {
  280. n = 0;
  281. L = _L;
  282. }
  283.  
  284. void addPoint(Point*me) {
  285. points[n++] = me;
  286. }
  287.  
  288. void start() {
  289. R = L + n - 1;
  290. sort(points, points + n, cmpPointPtrByY);
  291. memset(sum, 0, sizeof sum);
  292. }
  293.  
  294. void applyAdd(int add) {
  295. addAll += add;
  296. }
  297.  
  298. void relax() {
  299. if (!addAll)
  300. return;
  301. for (int i = 0; i < n; ++i) {
  302. points[i]->val += addAll;
  303. }
  304. addAll = 0;
  305. }
  306.  
  307. void rebuild() {
  308. sum[0] = 0;
  309. for (int i = 0; i < n; ++i) {
  310. sum[i + 1] = sum[i] + points[i]->val;
  311. }
  312. }
  313.  
  314. int ask(int ly, int ry) {
  315. static Point*tmp = new Point;
  316. tmp->y = ly;
  317. int atL = lower_bound(points, points + n, tmp, cmpPointPtrByY)
  318. - points;
  319. tmp->y = ry;
  320. int atR = upper_bound(points, points + n, tmp, cmpPointPtrByY)
  321. - points - 1;
  322. int cnt = atR - atL + 1;
  323. return sum[atR + 1] - sum[atL] + cnt * addAll;
  324. }
  325. };
  326.  
  327. Point points[MAX_N_POINTS];
  328. int nPoints;
  329.  
  330. Block blocks[MAX_SQRT_N_POINTS];
  331. int nBlocks;
  332.  
  333. void clear() {
  334. nPoints = 0;
  335. }
  336.  
  337. void addPoint(int x, int y) {
  338. points[nPoints++] = Point(x, y);
  339. }
  340.  
  341. void start() {
  342. sort(points, points + nPoints);
  343. nBlocks = 0;
  344. while (nBlocks * nBlocks < nPoints)
  345. ++nBlocks;
  346.  
  347. for (int i = 0; i < nBlocks; ++i) {
  348. blocks[i].set(i * nBlocks);
  349. }
  350. for (int i = 0; i < nPoints; ++i) {
  351. blocks[i / nBlocks].addPoint(points + i);
  352. }
  353. for (int i = 0; i < nBlocks; ++i) {
  354. blocks[i].start();
  355. }
  356. }
  357.  
  358. void doit(int lx, int rx, int d) {
  359. int at = lx / nBlocks;
  360. blocks[at].relax();
  361. for (int i = lx; i <= rx; ++i) {
  362. points[i].val += d;
  363. }
  364. blocks[at].rebuild();
  365. }
  366.  
  367. void change(int lx, int rx, int d) {
  368. lx = lower_bound(points, points + nPoints, Point(lx, -1)) - points;
  369. rx = upper_bound(points, points + nPoints, Point(rx, -1)) - points - 1;
  370. if (lx > rx)
  371. return;
  372. int atL = lx / nBlocks;
  373. int atR = rx / nBlocks;
  374. if (atL == atR) {
  375. doit(lx, rx, d);
  376. return;
  377. }
  378. doit(lx, blocks[atL].R, d);
  379. doit(blocks[atR].L, rx, d);
  380. ++atL;
  381. --atR;
  382. for (int i = atL; i <= atR; ++i) {
  383. blocks[i].applyAdd(d);
  384. }
  385. }
  386.  
  387. int ask(int ly, int ry) {
  388. int ret = 0;
  389. for (int i = 0; i < nBlocks; ++i) {
  390. ret += blocks[i].ask(ly, ry);
  391. }
  392. return ret;
  393. }
  394. };
  395.  
  396. DataStruct dataStrcut;
  397.  
  398. void calcFail() {
  399. static Trie*que[MAX_NLOGN];
  400. int qh = 0, qt = 0;
  401. que[qt++] = trieRoot;
  402. trieRoot->fail = 0;
  403. while (qh < qt) {
  404. Trie*u = que[qh++];
  405. for (int c = 0; c < MAX_N_ALPHA; ++c) {
  406. Trie*v = u->ch[c];
  407. if (v == 0)
  408. continue;
  409. Trie*p = u->fail;
  410. while (p != 0 && p->ch[c] == 0)
  411. p = p->fail;
  412. if (p == 0)
  413. p = trieRoot;
  414. else
  415. p = p->ch[c];
  416. v->fail = p;
  417. que[qt++] = v;
  418. }
  419. }
  420.  
  421. for (int i = 0; i < qh; ++i) {
  422. Trie*t = que[i];
  423. memset(t->fail2k, 0, sizeof t->fail2k);
  424. t->fail2k[0] = t->fail;
  425. for (int i = 0; i < MAX_LOG - 1; ++i) {
  426. if (t->fail2k[i] == 0)
  427. break;
  428. t->fail2k[i + 1] = t->fail2k[i]->fail2k[i];
  429. }
  430. }
  431. }
  432.  
  433. Trie*Left[MAX_L_PAT], *Right[MAX_L_PAT];
  434.  
  435. Trie*far[MAX_L_PAT];
  436.  
  437. Trie* isInST(int l, int r) {
  438. if (l > r)
  439. return trieRoot;
  440. Trie*at = far[r];
  441. Trie*cur = at;
  442. int len = r - l + 1;
  443. for (int i = MAX_LOG - 1; i >= 0; --i) {
  444. Trie*f = cur->fail2k[i];
  445. if (f == 0)
  446. continue;
  447. if (f->depth >= len)
  448. cur = f;
  449. }
  450.  
  451. if (cur->depth == len)
  452. return cur;
  453. return 0;
  454. }
  455.  
  456. void calcRight(Trie*Right[]) {
  457. Trie*t = trieRoot;
  458. for (int i = 0; i < patLen; ++i) {
  459. int cur = pat[i] - 'a';
  460. while (t && t->ch[cur] == 0)
  461. t = t->fail;
  462. if (t == 0)
  463. t = trieRoot;
  464. else
  465. t = t->ch[cur];
  466. far[i] = t;
  467. }
  468. for (int i = 0; i < patLen; ++i) {
  469. int l = i - 1, r = patLen;
  470. while (l + 1 < r) {
  471. int m = l + r >> 1;
  472. if (isInST(i, m) != 0)
  473. l = m;
  474. else
  475. r = m;
  476. }
  477. Right[i] = isInST(i, l);
  478. }
  479. }
  480.  
  481. void calcLeftAndRight() {
  482. calcFail();
  483. calcRight(Right);
  484. reverse(pat, pat + patLen);
  485. calcRight(Left);
  486. reverse(pat, pat + patLen);
  487. reverse(Left, Left + patLen);
  488. }
  489.  
  490. typedef long long int64;
  491.  
  492. int64 ans = 0;
  493.  
  494. void processSplit(const Split&split) {
  495. for (int i = 0; i < split.nBranch; ++i) {
  496. vector<Trie*>&tmp = split.trieByBranch[i];
  497. foreach(iter,tmp) {
  498. Trie*u = *iter;
  499. dataStrcut.change(u->begin, u->end, 1);
  500. }
  501. }
  502.  
  503. for (int i = 0; i < split.nBranch; ++i) {
  504. vector<Trie*>&tmp = split.trieByBranch[i];
  505. if (i != split.nBranch - 1) {
  506. foreach(iter,tmp) {
  507. Trie*u = *iter;
  508. dataStrcut.change(u->begin, u->end, -1);
  509. }
  510. }
  511.  
  512. foreach(iter,tmp) {
  513. Trie*u = *iter;
  514. ans += dataStrcut.ask(u->begin, u->end);
  515. }
  516.  
  517. if (i != split.nBranch - 1) {
  518. foreach(iter,tmp) {
  519. Trie*u = *iter;
  520. dataStrcut.change(u->begin, u->end, 1);
  521. }
  522. }
  523. }
  524.  
  525. for (int i = 0; i < split.nBranch; ++i) {
  526. vector<Trie*>&tmp = split.trieByBranch[i];
  527. foreach(iter,tmp) {
  528. Trie*u = *iter;
  529. dataStrcut.change(u->begin, u->end, -1);
  530. }
  531. }
  532. }
  533.  
  534. void prepareDataStruct() {
  535. dataStrcut.clear();
  536. for (int i = 0; i < patLen; ++i) {
  537. dataStrcut.addPoint(Left[i]->begin, Right[i]->begin);
  538. }
  539. dataStrcut.start();
  540. }
  541.  
  542. void calcAns() {
  543. ans = 0;
  544. for (int i = 0; i < splitsCur; ++i) {
  545. processSplit(splits[i]);
  546. }
  547. cout << ans << endl;
  548. }
  549.  
  550. void work() {
  551. doTreeSplit(vertexs + 0);
  552. getDfsOrd();
  553. calcLeftAndRight();
  554. prepareDataStruct();
  555. calcAns();
  556. }
  557.  
  558. void solve() {
  559. readInput();
  560. work();
  561. }
  562.  
  563. int main() {
  564. solve();
  565. }
  566.  
Not running #stdin #stdout 0s 0KB
stdin
Standard input is empty
stdout
Standard output is empty