[POJ3728]The merchant（tanrjan_lca + DP）

传送门

比着题解写还错。。。

查了两个小时没查出来，心态爆炸啊

以后再查

——代码（WA）

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 2000001 5 #define Min(x, y) ((x) < (y) ? (x) : (y)) 6 #define Max(x, y) ((x) > (y) ? (x) : (y)) 7 #define swap(x, y) ((x) ^= (y) ^= (x) ^= (y)) 8 9 int n, m, cnt, qcnt, acnt; 10 int f[N], fa[N], max[N], min[N], up[N], down[N], ans[N]; 11 int head[N], to[N << 1], next[N << 1], qhead[N], qu[N << 1], qv[N << 1], qid[N << 1], qnext[N << 1], ahead[N], ato[N << 1], anext[N << 1]; 12 13 inline int read() 14 21 22 inline void add(int x, int y) 23 28 29 inline void add_ask(int x, int y, int z) 30 37 38 inline void add_ans(int x, int y) 39 44 45 inline int find(int x) 46 56 return f[x]; 57 } 58 59 inline void dfs(int u) 60 69 for(i = head[u]; i ^ 1; i = next[i]) 70 74 for(i = ahead[u]; i ^ 1; i = anext[i]) 75 82 f[u] = fa[u]; 83 } 84 85 int main() 86 105 m = read(); 106 for(i = 1; i <= m; i++) 107 113 dfs(1); 114 for(i = 1; i <= m; i++) printf("%d\n", ans[i]); 115 } 116 return 0; 117 }
View Code

上一篇：[BZOJ2594] [Wc2006]水管局长数据加强版（LCT + kruskal + 离线）

下一篇：[luoguP1516] 青蛙的约会（扩展欧几里得）

---

lca DP tarjan