HDU 4123 Bob's Race
题意：定义每个点的值为它到树上最远点的距离，每次询问q，回答最长的极值差小于等于q且编号连续的一段点的长度。
题解：求距离两次dp，求极值ST表+尺取法。
HDU 4514 湫湫系列故事——设计风景线
题意：给一张图，如果有环，输出YES，否则为一个森林，求出每个树的直径，输出最大值。
题解：并查集判环，两边dfs找直径。
POJ 1655 Balancing Act
题意：删掉一个点，使得分出的最大连通块大小最小
题解：求重儿子，用重儿子大小和(n-sze[该子树])去更新答案。
HDU 4714 Tree2cycle
题意：删边或加边都有1的费用，求将一棵树变成一个环的最小费用。
题解：贪心：将树拆成链再连成环。具体：对树进行dfs，如果一个节点有大于等于2个子节点，就删边保留两个子节点，并删除该节点与父亲的连边（特判根节点），最后答案为删边*2+1（连接图的首尾）。
code
hdu4123
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 50050
#define maxm 550
#define oo 0x3f3f3f3f
int n, m;
int ecnt, adj[maxn], go[maxn*2], len[maxn*2], nxt[maxn*2];
int dp[maxn][5]; //0向下最大，1向下次大，2向上最大
int delta[maxn], Log[25], ans;
int mx[maxn][25], mn[maxn][25];
inline void initLog() {
Log[0] = -1;
for(int i = 1; i <= 50005; i++) Log[i] = Log[i >> 1] + 1;
}
inline void addEdge(int u, int v, int c) {
nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v, len[ecnt] = c;
}
inline void init() {
for(int i = 1; i <= n; i++) adj[i] = 0;
ecnt = 0;
for(int i = 1; i <= n; i++) {
dp[i][0] = dp[i][1] = 0;
dp[i][2] = 0;
}
}
inline void dfs1(int u, int f) {
for(int e = adj[u]; e; e = nxt[e]) {
int v = go[e];
if(v == f) continue;
dfs1(v, u);
if(dp[v][0] + len[e] > dp[u][0]) {
dp[u][1] = dp[u][0];
dp[u][0] = dp[v][0] + len[e];
} else if(dp[v][0] + len[e] > dp[u][1]) {
dp[u][1] = dp[v][0] + len[e];
}
}
}
inline void dfs2(int u, int f) {
for(int e = adj[u]; e; e = nxt[e]) {
int v = go[e];
if(v == f) continue;
int t = ((dp[u][0] == dp[v][0] + len[e]) ? dp[u][1] : dp[u][0]);
dp[v][2] = max(t + len[e], dp[u][2] + len[e]);
dfs2(v, u);
}
}
inline int query(int l, int r){
int k = Log[r - l + 1];
int maxx = max(mx[l][k], mx[r - (1 << k) + 1][k]);
int minn = min(mn[l][k], mn[r - (1 << k) + 1][k]);
return maxx - minn;
}
int main() {
initLog();
while(scanf("%d%d", &n, &m) != EOF) {
if(!n && !m) return 0;
init();
for(int i = 1; i < n; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
addEdge(x, y, z);
addEdge(y, x, z);
}
dfs1(1, 0);
dfs2(1, 0);
// for(int i = 1; i <= n; i++) cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<endl;
for(int i = 1; i <= n; i++) mx[i][0] = mn[i][0] = max(dp[i][0], dp[i][2]);
for(int j = 1; j <= Log[n]; j++)
for(int i = 1; i <= n; i++){
if(i + (1 << j) - 1 <= n){
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
}
}
for(int i = 1; i <= m; i++) {
int q, ans = 0;
scanf("%d", &q);
int head = 1;
for(int j = 1; j <= n; j++) {
while(head <= j && query(head, j) > q) head++;
ans = max(ans, j - head + 1);
}
printf("%d
",ans);
}
}
}
hdu4514
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 100050, M = 1000050;
int n, m;
int ecnt, adj[N], go[M << 1], nxt[M << 1], len[M << 1];
int vst[N], vt, anc[N], pos1, pos2, dis, ans;
inline void addEdge(int u, int v, int l){
nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v, len[ecnt] = l;
}
inline void dfs(int u, int f, int l, int &pos){
vst[u] = vt;
if(l > dis){
pos = u;
dis = l;
}
for(int e = adj[u]; e; e = nxt[e]){
int v = go[e];
if(v == f) continue;
dfs(v, u, l + len[e], pos);
}
}
inline int getAnc(int x){
return x == anc[x] ? x :(anc[x] = getAnc(anc[x]));
}
int main(){
while(~scanf("%d%d", &n, &m)){
for(int i = 1; i <= n; i++) anc[i] = i, adj[i] = 0; ecnt = ans = 0;
bool flag = true;
for(int i = 1; i <= m; i++){
int x, y, z; scanf("%d%d%d", &x, &y, &z);
if(!flag) continue;
int fx = getAnc(x), fy = getAnc(y);
if(fx == fy) flag = false;
if(flag) addEdge(x, y, z), addEdge(y, x, z), anc[fx] = fy;
}
if(!flag){
printf("YES
");
continue;
}
vt++;
for(int i = 1; i <= n; i++){
if(vst[i] == vt) continue;
dis = 0, pos1 = 0, pos2 = 0;
dfs(i, 0, 0, pos1);
dis = 0;
dfs(pos1, 0, 0, pos2);
ans = max(dis, ans);
}
printf("%d
", ans);
}
}
poj1655
待填
hdu4714
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read(){
int i = 0, f = 1; char ch = getchar();
for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
if(ch == '-') f = -1, ch = getchar();
for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');
return i * f;
}
inline void wr(int x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
const int N = 1000050;
int T, n;
int ecnt, adj[N], go[N << 1], nxt[N << 1], cnt;
inline void addEdge(int u, int v){
nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v;
}
inline int dfs(int u, int f){
int ret = 0;
for(int e = adj[u]; e; e = nxt[e]){
int v = go[e];
if(v == f) continue;
ret += dfs(v, u);
}
if(ret >= 2){
cnt += ret - 2 + (u == 1 ? 0 : 1);
return 0; //删去与父亲节点的边
}
return 1;
}
int main(){
T = read();
while(T--){
n = read();
for(int i = 1; i <= n; i++) adj[i] = 0; ecnt = 0;
for(int i = 1; i < n; i++){
int x = read(), y = read();
addEdge(x, y);
addEdge(y, x);
}
cnt = 0;
dfs(1, 0);
wr(cnt * 2 + 1);
putchar('
');
}
}