二次聯通門 : luoguP1046

?

?

/*這個題好難.....由蘋果樹可知這應該是個樹結構的題所以很自然的想到了用樹鏈剖分來搞一下連邊 最后查詢以1為根節點的子樹的權值和...從前閑的沒事寫著玩... */ #include <cstdio> #define Max 3300void read (int &now) {now = 0;char word = getchar ();while (word > '9' || word < '0')word = getchar ();while (word >= '0' && word <= '9'){now = now * 10 + word - '0';word = getchar ();} }static int Hight;struct Edge {int to;int next; };int Edge_Count; int edge_list[Max]; Edge edge[Max];inline void AddEdge (int from, int to) {Edge_Count++;edge[Edge_Count].to = to;edge[Edge_Count].next = edge_list[from];edge_list[from] = Edge_Count;Edge_Count++;edge[Edge_Count].to = from;edge[Edge_Count].next = edge_list[to];edge_list[to] = Edge_Count; }struct Point {int size;int deep;int dis;int father;int tree_number;int End; };struct Tree {int l;int r;int dis;int Mid; };Tree tree[Max]; Point point[Max]; int Count;void Dfs_1 (int now, int father) {int pos = Count++;point[now].father = father;point[now].deep = point[father].deep + 1;for (int i = edge_list[now]; i; i = edge[i].next){if (edge[i].to == father)continue;Dfs_1 (edge[i].to, now);}point[now].size = Count - pos; }int tree_dis[Max];void Dfs_2 (int now, int chain) {int pos = 0;point[now].tree_number = ++Count;tree_dis[Count] = point[now].dis;for (int i = edge_list[now]; i; i = edge[i].next){if (point[edge[i].to].tree_number)continue;if (point[edge[i].to].size > point[pos].size)pos = edge[i].to;}if (pos)Dfs_2 (pos, chain);for (int i = edge_list[now]; i; i = edge[i].next){if (point[edge[i].to].tree_number)continue;Dfs_2 (edge[i].to, edge[i].to);}point[now].End = Count; }void Tree_Build (int l, int r, int now) {tree[now].l = l;tree[now].r = r;if (l == r){tree[now].dis = tree_dis[++Count] <= (30 + Hight) ? 1 : 0;return ;}tree[now].Mid = (l + r) >> 1;Tree_Build (l, tree[now].Mid, now << 1);Tree_Build (tree[now].Mid + 1, r, now << 1 | 1);tree[now].dis = tree[now << 1].dis + tree[now << 1 | 1].dis; }int Tree_Query (int l, int r, int now) {if (tree[now].l == l && tree[now].r == r)return tree[now].dis;if (r <= tree[now].Mid)return Tree_Query (l, r, now << 1);else if (l > tree[now].Mid)return Tree_Query (l, r, now << 1 | 1);elsereturn Tree_Query (l, tree[now].Mid, now << 1) + Tree_Query (tree[now].Mid + 1, r, now << 1 | 1); }int main (int argc, char *argv[]) {for (int i = 1; i <= 10; i++)read (point[i].dis);read (Hight);for (int i = 1; i < 10; i++)AddEdge (i, i + 1);Count = 0;Dfs_1 (1, 1);Count = 0;Dfs_2 (1, 0);Count = 0;Tree_Build (1, 10, 1);printf ("%d", Tree_Query (point[1].tree_number, point[1].End, 1));return 0; }

?

轉載于:https://www.cnblogs.com/ZlycerQan/p/6805256.html

總結

以上是生活随笔為你收集整理的luogu P1046 陶陶摘苹果的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。