prufer编码

prufer编码  
prufer编码是用另外一种形式来描述一棵树，这棵树是无根树，它可以和无根树之间形成一一对应关系。

编码方式是：
首先选这棵树叶子中编号最小的点，将这个点删除，并且把它的邻接点加入一个数组中，例如第一个删除的节点为1，并且把5加入数组中。删除节点后形成一棵新的树，再在新树中删除最小的节点，并且把邻接点加入数组中，，这样重复以上步骤，知道树中最后剩余两个点的时候终止操作。这时候数组中的便是prufer编码。

由prufer编码来重建这棵树的方法是：
假如prufer编码为(a1,a2,a3,a4,a5,.....an-2)在上述数组中，在数组最后加入n这个值，这样便形成了数组中包含n-1个节点，例如上述为5,5,4,4,4,6,8。
然后取不在数组中的最小值为b1，则b1与a1是邻接点，在数组中删除a1，再在剩下的数中选取不为b1，且不在数组中的最小值为b2，则b2与a2是邻接点，这样依次循环下去直到结束，这样便形成了一棵树。

Cayley定理：不同的n节点标号树的数量为n^(n-2)。

prufer序列中某个编号出现的次数+1就等于这个编号的节点在无根树中的度数。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;

const int INF = 0x3f3f3f3f;
const int MXN = 1e5 + 5;
const int MXE = 5e6 + 6;
const int mod = 998244353;


///tran prufer code
int n, m;
int prufer[MXN];
int vis[MXN];///is this node in prufer sequence
int used[MXN];///have this node been used
struct lp{
    int v, nex;
}cw[MXE];
int head[MXN], tot;
void add_edge(int u,int v) {
    cw[++tot].v = v; cw[tot].nex = head[u];
    head[u] = tot;
    cw[++tot].v = u; cw[tot].nex = head[v];
    head[v] = tot;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n - 2; ++i) {
        scanf("%d", &prufer[i]);
        vis[prufer[i]] ++;
    }
    set<int> st;///which node is not in prufer sequence
    for(int i = 1; i <= n; ++i) {
        if(!vis[i]) st.insert(i);
    }
    for(int i = 1; i <= n - 2; ++i) {
        int v = *st.begin(), u = prufer[i];
        add_edge(u, v);
        printf("%d - %d
", u, v);
        vis[u] --;
        used[v] = 1;
        st.erase(v);
        if(!vis[u] && !used[u]) {
            st.insert(u);
        }
    }
    int u = *st.begin();
    st.erase(u);
    int v = *st.begin();
    add_edge(u, v);
    printf("%d - %d
", u, v);
    return 0;
}
/*
///make prufer code
int n, m;
int in[MXN], prufer[MXN], vis[MXN];
struct lp{
    int v, nex;
}cw[MXE];
int head[MXN], tot;
void add_edge(int u,int v) {
    cw[++tot].v = v; cw[tot].nex = head[u];
    head[u] = tot;
    cw[++tot].v = u; cw[tot].nex = head[v];
    head[v] = tot;
}
int main(){
    scanf("%d%d", &n, &m);
    memset(head, -1, sizeof(head));
    tot = -1;
    for(int i = 0, u, v; i < m; ++i) {
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        in[u] ++; in[v] ++;
    }
    set<int> st;
    for(int i = 1; i <= n; ++i) {
        if(in[i] == 1) vis[i] = 1, st.insert(i);
    }
    int k = 0, ans;
    while(1) {
        ans = *st.begin();
        st.erase(ans);
        for(int i = head[ans]; ~i; i = cw[i].nex) {
            int v = cw[i].v;
            if(vis[v]) continue;
            in[v] --;
            prufer[k++] = v;
            if(in[v] == 1) {
                vis[v] = 1;
                st.insert(v);
            }
        }
        if(k == n - 2) break;
    }
    for(int i = 0; i < n - 2; ++i) {
        printf("%d ", prufer[i]);
    }
    printf("
");
    return 0;
}
*/

求树的直径长度 ``` const int MXN = 1e6 + 5; const int mod = 1e9 + 7;

int n, m;
int fa[MXN], idx[MXN], vis[MXN];
std::vector mp[MXN];
int mmax;
int dfs(int u,int ba) {
int dis1 = 0, dis2 = 0;
for(auto v: mp[u]) {
if(v == ba) continue;
int tmp = dfs(v, u);
if(tmp > dis2) dis2 = tmp;
if(dis2 > dis1) swap(dis1, dis2);
}
if(dis1+dis2>mmax) mmax = dis1+dis2;
return dis1 + 1;
}
int Fi(int x) {
return fa[x] == x? x: fa[x] = Fi(fa[x]);
}
int main(){
while(~scanf("%d%d", &n, &m)) {
for(int i = 1; i <= n; ++i) fa[i] = i,vis[i]=0;
for(int i = 1, a, b; i <= m; ++i) {
scanf("%d%d", &a, &b);
++ a; ++ b;
mp[a].push_back(b); mp[b].push_back(a);
a = Fi(a); b = Fi(b);
fa[a] = b;
}
int k = 0;
for(int i = 1; i <= n; ++i) {
if(vis[Fi(i)]) continue;
vis[Fi(i)] = 1;
mmax = 0;
dfs(Fi(i), -1);
idx[k ++] = mmax;
}
sort(idx,idx+k,greater());
int ans = idx[0];
if(k > 1) ans = max(ans, (idx[0]+1)/2+(idx[1]+1)/2+1);
if(k > 2) ans = max(ans, (idx[1]+1)/2+(idx[2]+1)/2+2);
printf("%d ", ans);
}
return 0;
}