思路
显然，可以通过树形dp求得树上每一点可以达到的最远距离
参考博客
得到d数组后，我们就可以发现这个区间长度符合二分性，所以我们可以二分区间长度在利用滑动窗口check合理性。注意求最大值，我一般用左闭右开区间。求最小值，我用的一般是左开右闭。
树形dp模板(理解就可以认为是把子节点拎起来变成根)
dp[maxn][3]
dp[u][0]表示以u为根的子树中的结点与u的最远距离
dp[u][1]表示以u为根的子树中的结点与u的次远距离
dp[u][2]表示u往上走的最远距离
dp[2][v] = max( dp[0][u]+weight(u,v) , dp[2][u]+weight(u,v) ) （v是u的儿子 且 u往下走的最远距离不经过v）
dp[2][v] = max( dp[1][u]+weight(u,v) , dp[2][u]+weight(u,v) ) （v是u的儿子 且 u往下走的最远距离经过v）二分模板
求最小值模板（左开右闭）
int l = -1， r = n；
while(r - l > 1){
int mid = (l + r) / 2;
if(check(mid)){
r = mid;
}
else{
l = mid;
}
}
printf("ans = %d\n", r);求最大值模板（左闭右开）
int l = 1, r = n + 1;
while(r - l > 1){
int mid = (l + r) / 2;
if(check(mid)){
l = mid;
}
else{
r = mid;
}
}
printf("ans = %d\n", l);滑动窗口问题（单调队列维护最大、最小值）
int qd[maxn], qx[maxn];
int beg = 1, top = 0;///当且仅当beg<=top时表示队列有元素
int be = 1, to = 0;
for(int i = 1; i <= n; i++){
while(beg <= top && b[i] >= b[qd[top]]) top--;
while(be <= to && b[i] <= b[qx[to]]) to--;
///维护单调队列
qd[++top] = i;
qx[++to] = i;
if(i >= k){
///去除窗口外元素(qd[top] = i)
while(qd[top] - qd[beg] + 1 > k) beg++;
while(qx[to] - qx[be] + 1 > k) be++;
printf("max = %d min = %d\n", b[qd[beg]], b[qx[be]]);
}
}
京公网安备 11010502036488号