二次联通门 :

 

 

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