戳我传送题意:给你一颗树,然后n个点,n-1条边.然后给你q组查询,每组查询给你三个数分别是:u,v,c 题目保证1是首都,并且u->v->1这种类型的查询(此时v是u的父亲),问你从u->v的最长上升子序列长度。思路:倍增+dfs题目表明v一定在u去网1的最短路径上,如果从u一直往上走到v,再去判断到达的每一个城市,需不需要购买。这种算法的极端情况,形成了一条长为n的链,时间复杂度达到了O(nq),后面数据加强就会超时了。正确的做法是用倍增,f[i][k]表示i结点的第 个比i大的父亲的位置(是那个结点),这个理解清楚看代码得看半天。不难得出状态转移方程f[i][k]=f[...