T1

米小游拿到了一个字符串，她想截取一个连续子串，使得该子串中包含至少k个连续的“mihoyo”。你可以帮米小游求出最短的子串长度，以及对应的子串位置吗？
输入描述：
第一行输入两个正整数n和k，用空格隔开。
第二行输入一个长度为n的、仅由小写字母组成的字符串。
1≤k≤n≤200000
输出描述：
如果不存在这样一个连续子串，请输出-1。
否则输出两个正整数l，r，代表选取的子串的左下标和右下标(整个字符串左下标为0，右下标为n-1）。
请务必保证选择的连续子串包含至少k个"mihoyo"，且长度是最短的。有多解时输出任意即可。

input:
22 2
mihoyoyomihoyomimihoyo

output:
0 13

维护所有"mihoyo"字符串出现的位置，计算任意连续k个位置的最短就可以了。

n, k = map(int, input().split())
s = input()
a = []
start = 0
t = 'mihoyo'
while True:
    i = s.find(t, start)
    if i == -1: break
    a.append(i)
    start = i + 1
ans = float('inf')
ansl, ansr = 0, 0

if len(a) >= k:
    for i in range(len(a) - k + 1):
        l = a[i]
        r = a[i + k - 1] + 5
        if r - l + 1 < ans:
            ans = r - l + 1
            ansl, ansr = l, r

if ans == float('inf'): print(-1)
else: print(ansl, ansr)

T2

米小游心中想了一个正整数，她邀请了n个人来猜这个数。每个人会猜一个数ai，然后米小游会告诉对方猜的结果：大于等于米小游想的数（≥）或者小于米小游想的数（<）。
猜谜结束后，米小游统计了共有x个≥和y个<。请你判断米小游初始想的数有多少种不同的可能？

输入描述：
第一行输入一个正整数n，代表猜谜的人数。
第二行输入n个正整数ai，代表每个人猜的数字。
第三行输入两个整数x和y，用空格隔开。
1≤x+y=n≤1e5
1 ≤ ai ≤ 1e9
输出描述：
如果有无穷多种可能，输出"infinity"
否则输出一个整数，代表米小游心中想的数的不同可能数量。

input:
3
1 5 3
0 3

output:
infinity

因为题目数据保证满足要求，那么把a数组排序。表示>=的必然是前面几个，表示<的必然是后面几个。

什么时候会出现infinity？就是每一个数都输出大于的时候。因为说了是正整数，如果全是<，下层最小值是1，是有限的。

唯一的坑点，数据的代表>=的x和代表<的y写反了……把这两个数据调过来就可以过100%。

n = int(input())
*a, = map(int, input().split())
x, y = map(int, input().split())
a.sort()

if x == 0:
    print('infinity')
else:
    if y:
        l = a[y - 1]
    else:
        l = 1
    r = a[y]
    print(r - l)

T3

米小游有一棵有根树，树上共有n个节点。
米小游指定了一个节点x为根，然后定义所有相邻的、编号奇偶性相同的节点为一个连通块。米小游想知道，所有子树（共有n个子树）的连通块数量之和是多少？
举个例子：

如上图，3号节点被指定为根
然后3-1-5作为一个连通块，4号节点和2号节点为单独的连通块。
那么1号节点到5号节点，每个节点的子树连通块数量分别为：2、1、3、1、1，总连通块数量是8。

input:
5 3
1 2
1 3
3 4
5 1

output:
8

经典自底向上递归。以某节点为根的子树的贡献=所有子树贡献和-与该节点奇偶性相同的子节点数量。

import sys

sys.setrecursionlimit(int(2e5))

n, x = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)


def solve():
    ret = 0

    def dfs(cnt, pre):
        ans = 1
        for nxt in g[cnt]:
            if nxt == pre: continue
            ans += dfs(nxt, cnt)
            if (cnt & 1) == (nxt & 1): ans -= 1
        nonlocal ret
        ret += ans
        return ans

    dfs(x, -1)
    return ret


print(solve())