第一题
紧急疏散
体育场突然失火了,现场需要紧急疏散,但是过道真的是太窄了,同时只能容许一个人通过。现在知道了体育场的所有座位分布,座位分布图是一棵树,已知每个座位上都坐了一个人,安全出口在树的根部,也就是1号结点的位置上。其他结点上的人每秒都能向树根部前进一个结点,但是除了安全出口以外,没有任何一个结点可以同时容纳两个及以上的人,这就需要一种策略,来使得人群尽快疏散,问在采取最优策略的情况下,体育场最快可以在多长时间内疏散完成。
输入
第一行包含一个整数n,即树的结点数量(1<=n<=100000)。
接下来有n-1行,每行有两个正整数x,y,表示在x和y结点之间存在一条边。(1<=x<=y<=n)
输出
输出仅包含一个正整数,表示所需要的最短时间
示例
输入62 13 24 35 46 5输出5
第二题
寻找字串
给出m个字符串S1,S2,…,Sm和一个单独的字符串T,请在T中选出尽可能多的子串同时满足:
这些子串在T中互不相交这些子串都是S1,S2…Sm中的某个串
问最多能选出多少串
输入
第一行一个数m(1<m<=10),每行一个串。最后一行输入一个串T。输入中所有单个串的长度不超过100000,串中只会出现小写字母。
输出
输出一个数,最多能选出多少串。
示例
输入3aabacbbaac输出3