POJ-2201-Cartesian Tree(笛卡尔树)

Description Let us consider a special type of a binary search tree, called a cartesian tree. Recall that a binary search tree is a rooted ordered binary tree, such that for its every node x the fo

POJ 2367 Genealogical tree 拓扑题解

一条标准的拓扑题解。 我这里的做法就是： 保存单亲节点作为邻接表的邻接点，这样就非常方便能够查找到那些点是没有单亲的节点，那么就能够输出该节点了。 详细实现的方法有非常多种的，比方记录每一个节点的入度，输出一个节点之后，把这个节点对于其它节点的入度去掉，然后继续查找入度为零的点输出。这个是一般的做法了，效果和我的程序一样的。 有兴趣的也能够參考下我这样的做法。 #includ

POJ 2029--Get Many Persimmon Trees +DP

题意: 在一个w*h宽的矩形中有些位置有树有些位置没有,然后我们须要从中选一个s*t的矩形,使得里面含有的树最多. 思路: 我们将有树位置的值看成1,其他为0,然后成了选一个区域值最大.然后考虑这个问题的一维形式,在一维的情况下,我们非常easy得到一个方案:先处理前缀和,然后就能够枚举区间端点的起点,O(1)时间计算区间和,然后取当中的最大值为答案. 这道题我们能够按相同

POJ 2486 Apple Tree

【BZOJ2588】Spoj 10628. Count on a tree 主席树+LCA

【BZOJ2588】Spoj 10628. Count on a tree Description 给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。 Input 第一行两个整数N,M。 第二行有N个整数，其中第i个整数表示点i的权值。

【POJ3237】Tree 树链剖分+线段树

【POJ3237】Tree Description You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associat

POJ 2378 Tree Cutting

Tree Cutting Time Limit: 1000ms Memory Limit: 65536KB This problem will be judged on PKU. Original ID: 237864-bit integer IO format: %lld      Java class name

HDU 1773 小希的迷宫 AND HDU 1325/POJ 1308 Is It A Tree?

题目链接： HDU 1773 小希的迷宫 HDU 1325  Is It A Tree? POJ  1308 Is It A Tree? 简述：  两道题均为基础的并查集问题，但是都要注意细节。 HDU 1773 小希的迷宫 ： 自环：例如  1 2 2 1 0

POJ - 3321 Apple Tree (线段树 + 建树 + 思维转换)

POJ - 3321 Apple Tree Time Limit: 2000MS   Memory Limit: 65536KB   64bit IO Format: %I64d & %I64u Submit Status Description There is an apple tree

【bzoj2588】Spoj 10628. Count on a tree 离散化+主席树

题目描述 给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。 输入 第一行两个整数N,M。 第二行有N个整数，其中第i个整数表示点i的权值。 后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。 最后M行每行两个整数(u,v,k)，表