首页 > 代码库 > [ NOIP ] SJZEZ五月小测笔记
[ NOIP ] SJZEZ五月小测笔记
树
【问题描述】
读入一颗 n个点的带权树，求
1. 直径长度。（距离最远的两点） 直径长度。（距离最远的两点）
2. 若删去任意一个点，原树会分裂成些连通块。求数最多的大小的最值。
3. 读入 Q个询问，每包括 (x,y) (x,y) ，表示查询从 ，表示查询从 x到 y路径上点权的最大值。
【输入格式】
输入文件 tree.in。
第一行两个整数 n,Q 。
第二行 n个整数 v[i] v[i] ，代表点权。
接下来 n-1行，每两个数 u,v 。代表树中有一条 (u,v) (u,v)的边。
接下来 Q行，每两个数 x,y 。
代表一次询问
【输出格式】
输出文件 tree.outtree.out tree.out tree.out 。
第一行输出直径长度。
第二行输出删去一个点后数最多的连通块大小值。
接下来 Q行，表示 Q次询问的答案。
【样例输入】
5 21 2 3 4 51 22 44 52 31 43 5
【样例输出】
3245
【数据规模和约定】
对于 30% 的数据， 1≤??,??≤1000。
对于 100% 的数据， 1≤??,??≤100000，0≤??[??]≤100000。
-----------------------------------------------------------------
一、树形dp
dfs搜索，对于每一个子树，p表示当前字树的根，x表示当前指向的孩子，len[p]表示p到叶子的最长距离，maxlen表示最长直径，则：
为了避免出现当前孩子连接一条最长距离，且此距离异常更新了maxlen，我们必须先用没有更新len[x]的len[p]来更新maxlen，
这时的len[p]是孩子1...x-1中的最长距离，所以1...x-1中的非最长距离不会影响maxlen，所以如果len[x]更新了len[p]，则上一步的maxlen更新
已经包括了len[x]这条路径。所以：
maxlen = max{ maxlen, len[p] + len[x] + 1 }
len[p] = max{ len[p], len[x] + 1 }
二、枚举
三、倍增法更新树上的一段路径的点权最大值，标准倍增法
code：
//Kvar_ispw17#include <iostream>#include <vector>#include <cstdio>using namespace std;const int maxn = 100000 + 10;const int inf = 0x7f7f7f7f;int n, q, w[maxn][21], fa[maxn][21], dep[maxn], siz[maxn], len[maxn], max_len, mx[maxn];vector<int> v[maxn];void add(int a, int b) { v[a].push_back(b);}void dfs(int p) { dep[p] = dep[fa[p][0]] + 1; siz[p] = 1; vector<int>::iterator it; for(it = v[p].begin(); it != v[p].end(); it++) { int x = *it; if(x != fa[p][0]) { fa[x][0] = p; dfs(x); siz[p] += siz[x]; mx[p] = max(mx[p], siz[x]); max_len = max(max_len, len[p] + len[x] + 1); len[p] = max(len[p], len[x] + 1); } } return;}int ask(int x, int y) { if(dep[y] > dep[x]) swap(x, y); int ans = w[x][0]; for(int j = 20; j >= 0; j--) { if(dep[fa[x][j]] >= dep[y]) { ans = max(ans, w[x][j]); x = fa[x][j]; } } if(x == y) return max(ans, w[x][0]); for(int j = 20; j >= 0; j--) { if(fa[x][j] != fa[y][j]) { ans = max(ans, max(w[x][j], w[y][j])); x = fa[x][j], y = fa[y][j]; } } return max(ans, max(w[x][1], w[y][1]));}int main() { freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); scanf("%d%d", &n, &q); for(int i = 1; i <= n; i++) scanf("%d", &w[i][0]); for(int i = 1; i < n; i++) { int a, b; scanf("%d%d", &a, &b); add(a,b); add(b,a); } dfs(1); printf("%d\n", max_len); int m = n; for(int i = 1; i <= n; i++) m = min(m, max(mx[i], n - siz[i])); printf("%d\n", m); for(int j = 0; j <= 20; j++) { for(int i = 1; i <= n; i++) { if(fa[i][j]) { fa[i][j + 1] = fa[fa[i][j]][j]; w[i][j + 1] = max(w[i][j], w[fa[i][j]][j]); } } } while(q--) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", ask(a, b)); } fclose(stdin); fclose(stdout); return 0;}
[ NOIP ] SJZEZ五月小测笔记