二次联通门 : luoguP1046
/* 这个题好难..... 由苹果树可知 这应该是个树结构的题 所以很自然的想到了用树链剖分来搞一下 连边 最后查询以1为根节点的子树的权值和... 从前闲的没事写着玩... */ #include <cstdio> #define Max 3300 void 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); else return 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; }