POJ - 3162（树形dp + 二分 + 滑动窗口）

思路
显然，可以通过树形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]]);
	}
}

I题tsh的代码