定义：

自行 $\text{OI-Wiki}$ 。

树的直径

有两种解法。

sol1

跑两遍大法师，第一遍找最远的结点，这个结点就是直径的一端，第二遍找以 第一遍找出的点 为根节点的最远的节点，这个点就是直径的第二端。
$\frac{1}{2}$

证明：

再次自行 OI-Wiki

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e7 + 7;
int id, maxn, n, deep[N];
struct edge 
{
        int to, next;
} e[N];
int cnt, he[N];

void add(int u, int v) 
{
        e[++cnt].next = he[u];
        e[cnt].to = v;
        he[u] = cnt;
}

void dfs(int u, int fa) 
{

        if(deep[u] > maxn)
                id = u, maxn = deep[u];

        for(int i = he[u]; i; i = e[i].next) 
        {
                int v = e[i].to;
                if(v == fa)
                        continue;
                deep[v] = deep[u] + 1;
                dfs(v, u);
        } // 我要 ak ioi 的
}

int main()
{
        cin >> n;
        for(int i = 1; i <= n - 1; i++)
        {
                int u,v;
                cin >> u >> v;
                add(u, v), add(v, u);
        }

        dfs(1, 0);

        memset(deep, 0, sizeof(deep));
        maxn = 0;

        dfs(id, 0);

        printf("%d", maxn);
        return 0;
}

sol2

用 $dp$ 写，分别记录每个点向下所能延伸的最大值与次大值，直径就是两者的加和。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int x,y,n,i,ans,d1[100001],d2[100001],t;
vector<int> E[100001];

void dfs(int now, int fath)
{
        d1[now]=d2[now]=0;
        for(int i = 0; i < E[now].size(); ++i)
        {
                int v=E[now][i];
                if (fath==v) continue;
                dfs(v,now);
                t=d1[v]+1;
                if (t>d1[now]) d2[now]=d1[now],d1[now]=t;
                else if (t>d2[now]) d2[now]=t;
        }
        ans=max(ans,d1[now]+d2[now]);
}

int main()
{
        cin >> n;
        for (i=1; i<n; i++)
        {
                int u,v;
                cin >> u >> v;
                E[u].push_back(v);
                E[v].push_back(u);
        }
        dfs(1,0);
        cout << ans;
        return 0;
}

LCA最近公共祖先

可以用 tarjan 写（显然我只看了这一个...）
做法：用临接链表存下每条边和询问的信息，然后跑一遍 $tarjan$ ，最后对于询问 $i,j$ 的 $lca$ ，答案为 $dd[i]+dd[j]-2*dd[LCA(i,j)]$ ，这里 $dd[i]$ 为 $i$ 点到根节点的距离。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int x,y,k,question[N],edge[N],tot,tot1,fa[N],dd[N],lca[N],que1[N],que2[N];//d[i]表示该节点到根节点的距离，fa是父亲节点
bool ff[N];
struct EDGE
{
        int to,v,next;
};
EDGE a[N];
struct QUES
{
        int to,nu,next;
};
QUES b[N];

void add_edge(int x,int y,int value)
{
        a[++tot].to=y;//这条边到哪个点
        a[tot].v=value;//这条边的长度
        a[tot].next=edge[x];//与这条边有相同初始点的上一条边编号 
        edge[x]=tot;//更新
}
void add_question(int x,int y,int number)
{
        b[++tot1].to=y;//询问点编号
        b[tot1].nu=number;
        b[tot1].next=question[x];
        question[x]=tot1;
}

int get (int x)
{
        if (fa[x]==x) return x;
        return fa[x]=get(fa[x]);
}//并查集

void tarjan(int x)
{
        fa[x]=x;//将父节点指向自己
        ff[x]=true;//标记该点已经走过
        for(int i=question[x]; i; i=b[i].next)
        {
                int now=b[i].to;
                if(ff[now])
                        lca[b[i].nu]=get(now);//更新lca
        }
        for(int i=edge[x]; i; i=a[i].next)
        {
                int now=a[i].to;
                if(!ff[now])
                {
                        dd[now]=dd[x]+a[i].v;//更新dd
                        tarjan(now);
                        fa[now]=x;//更新父节点
                }
        }
}
int main()
{
        int tt;
        cin >> tt;
        while (tt--)
        {
                int n,m;
                cin >> n >> m;
                memset(ff,false,sizeof(ff));
                memset(edge,0,sizeof(edge));
                memset(question,0,sizeof(question));
                memset(a,0,sizeof(a));
                memset(b,0,sizeof(b));
                memset(dd,0,sizeof(dd));
                memset(fa,0,sizeof(fa));
                for (int i=1; i<=n; i++) fa[i]=i;
                tot=0; tot1=0;//预处理
                for(int i=1; i<=n-1; i++)
                {
                        int aa,bb,cc;
                        scanf("%d%d%d",&aa,&bb,&cc);
                        add_edge(aa,bb,cc);
                        add_edge(bb,aa,cc);
                }//建树
                for(int i=1; i<=m; i++)
                {
                        int aa,bb;
                        scanf("%d%d",&aa,&bb);
                        add_question(aa,bb,i);
                        add_question(bb,aa,i);//安全一点存两次
                        que1[i]=aa,que2[i]=bb;
                }
                tarjan(1);
                for (int i=1; i<=m; i++)
                        printf("%d\n",dd[que1[i]]+dd[que2[i]]-2*dd[lca[i]]);
        }
}

树的重心

定义：

对于一棵树n个节点的无根树，找到一个点，将无根树变为以该点为根的有根树时，最大子树的结点数最小。换句话说，删除这个 1 点后最大连通块（一定是树）的结点数最小。

Sol

用大法师计算每个子树大小，利用总点数 - 当前子树的大小得到“向上”的子树的大小，然后就可以依据定义找到重心了。

Code

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a ".in","r",stdin),freopen(a ".out","w",stdout);
using namespace std;

const int maxn=20010;
struct edge {int to,next;} e[maxn<<2];

int head[maxn],vis[maxn],son[maxn],cnt,size,ans,n;

void insert(int u,int v) {
        e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt;
        e[++cnt].to=u; e[cnt].next=head[v]; head[v]=cnt;
}
void dfs(int x) {
        vis[x]=1,son[x]=0;
        int tmp=0;
        for (int i=head[x]; i; i=e[i].next) if (!vis[e[i].to]) {
                        dfs(e[i].to);
                        son[x]+=son[e[i].to]+1;
                        tmp=max(tmp,son[e[i].to]+1);
                }
        tmp=max(tmp,n-son[x]-1);
        if (tmp<size || (tmp==size && x<ans)) size=tmp,ans=x;
}
int main() {
        int T; scanf("%d",&T);
        while (T--) {
                scanf("%d",&n);
                memset(vis,0,sizeof(vis)); memset(head,0,sizeof(head));
                cnt=ans=0; size=inf;
                for (int i=1; i<n; i++) {
                        int u,v;
                        scanf("%d%d",&u,&v);
                        insert(u,v);
                }
                dfs(1);
                printf("%d %d\n",ans,size);
        }
        return 0;
}