树的直径
题单介绍
## ST表
给定静态数组，多次查询区间最值
预处理复杂度O(nlogn) 单次查询O(1)
```cpp
int mx[100005][21];
// mx[i][j]表示从i开始数2^j个元素中的最大值
// mx[3][2] = max{a[3],a[4],a[5],a[6]}
// mx[i][j] = max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
// 在任何倍增问题里，如果担心越界，最好的方法是不处理
int query(int l,int r){
int k = log2(r-l+1); // log2有一定常数
return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
int main(){
for(int i=1;i<=n;i++) mx[i][0] = a[i];
for(int j=1;j<=20;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
mx[i][j] = max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
}
```
## 离散化
```cpp
for(int i=1;i<=n;i++) b[i] = a[i];
sort(b+1,b+n+1);
// b : 1,1,2,200,300,300,400
// 1. map
map<int,int>mp;
int len = unique(b+1,b+n+1) - b - 1;
for(int i=1;i<=len;i++) mp[b[i]] = i;
// 2. lower_bound
// b : 1,1,2,200,300,300,400
int len = unique(b+1,b+n+1) - b - 1;
for(int i=1;i<=n;i++) a[i] = lower_bound(b+1,b+len+1,a[i])-b;
```
## set
维护集合（一些独立的数值）
```cpp
set<int>s; // 数学中的集合是没有重复元素
s.insert(10); // 插入
s.insert(10); // 插入重复数字无效
cout << s.size();
s.erase(10); // 删除数字10
cout << *s.begin(); // set内部是有序的 begin就是最小值 --end()是最大值
cout << *--s.end();
cout << *s.rbegin(); // rbegin反向迭代器
// 输出次大值
cout << *prev(s.end(),2);
// 输出次小值
cout << *next(s.begin());
// 找到第一个大于等于10的位置
s.lower_bound(10);
multiset<int>ms; // 可重集合 {10,10,20}
ms.insert(10);
ms.insert(10);
ms.insert(20);
ms.erase(10); // 删掉里面所有的10
ms.erase(ms.lower_bound(10)); // 传入的是第一个10的位置
cout << ms.count(10);
```
## pair
```cpp
#define pii pair<int,int>
// 但凡需要两个参数的结构体 不妨换成pair
// .first .second
vector<pii> a;
a.push_back({1,3});
a.push_back({2,5});
a.push_back({3,1});
a.push_back({4,10});
sort(a.begin(),a.end()); // pair类型是有默认的比较规则的
// 想把一些数值排序，同时记录他们原本的下标位置
// pair<数值，下标> 直接排序 可以把想排序的东西放在first的位置
// dijkstra
priority_queue <pii> pq;
memset(dis,0x3f,sizeof(dis));
dis[s] = 0;
pq.push({s,0});
for(int i=1;i<=n;i++){
auto cur = pq.top();
int nowdis = -cur.first;
int id = cur.second;
for(int j=0;j<e[id].size();j++){
int to = e[id][j].first;
int len = e[id][j].second;
if(nowdis + len < dis[to]){
dis[to] = nowdis + len;
pq.push({-dis[to],to});
}
}
}
// map内部存储 若干个pair组成的 map也是默认有序的
map<int,int> mp;
mp[2] = 4;
mp[4] = 3;
// (2,4) (4,3)
for(auto it=mp.begin();it!=mp.end();it++){
cout << it->first << ' ' << it->second;
}
for(auto it:mp){ // 这里的it直接是每一项的数值
cout << it.first << ' ' << it.second;
}
```
## 树的基础
- 树上dfs
- 树的直径
- 性质1：所有的直径中点重合
- 性质2：对于树上的任意点x，距离x最远的点一定是某条直径的端点
- 随便找到一条直径(p,q) 那么对于x的最远距离要么是dis(x,p) 要么是dis(x,q)
- 树的重心
```cpp
vector<int>E[maxn];
// 维护一些额外的信息 dep[x],sz[x]
void dfs(int x,int f){
sz[x] = 1;
dep[x] = dep[f] + 1;
for(auto y:E[x]){
if(y == f) continue;
dfs(y,x);
sz[x] += sz[y];
}
}
```