初探

三值逻辑

奇数环问题，可以连双向边跑奇数环（这是为了在任意一个点都能跑完全图）

在最开始累计和U相连的点，接着累计带奇数环的子图即可。

难度评分：丙上

网络稳定性

最大Kruskal树上用lca求路径最小边。

难度评分：丙上

假期计划

bfs处理最短路。只要处理出可达，在家附近的从大到小的3个点即可。

难度评分：丙上

树形结构

建造军营

边双缩点，处理完之后DP分类讨论即可。

注意的是分类讨论可能会重，所以要在LCA处处理。

难度评分：乙中

树的重心

用树上倍增算法维护重儿子，换根时维护每个结点的子树大小、父亲、重儿子。

计算一个树的贡献的方法为：用倍增往下走到满足条件的最深结点即可，同时还需要特判一下这个结点的父亲（有两个的情况）。

只要能换根就可以做，这是一个经典的Trick。

我们的目标就是在O(logn)的时间里换根，

只要知道重儿子就可以做，这需要我们维护节点大小。

我们需要算一下减去（u，v）后的u的贡献和原来的v的贡献

接着就是换根，注意这会增加的情况是以u为贡献的时候，这里有一个技巧，直接搜所有与它相关的边，因为它已经变成根了，这样就可以包括以u为贡献的时候。

一年半前的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,K=25;
vector<int> e[N];
int T,n,f[N][K],p[N],son[N],sz[N];long long ans;
void init(int u){for(int i=1;i<K;i++) f[u][i]=f[f[u][i-1]][i-1];}
void calc(int x){
    int u=x;
    for(int i=K-1;i>=0;i--)
        if(f[u][i]&&sz[f[u][i]]*2>=sz[x]) u=f[u][i];
    if(sz[u]*2==sz[x]) ans+=p[u];
    ans+=u;
}
void dfs(int u,int fa){
    sz[u]=1;p[u]=fa;son[u]=0;
    for(auto v:e[u])
        if(v!=fa){
            dfs(v,u);sz[u]+=sz[v];
            if(sz[v]>sz[son[u]]) son[u]=v;
        }
    f[u][0]=son[u];init(u);
}
void gts(int u,int fa){
    int mx1=0,mx2=0;
    for(auto v:e[u]){
        if(sz[v]>=sz[mx1]) mx2=mx1,mx1=v;
        else if(sz[v]>=sz[mx2]) mx2=v;
    }
    for(auto v:e[u])
        if(v!=fa){
            calc(v);f[u][0]=(v==mx1)?mx2:mx1;init(u);
            sz[u]-=sz[v];sz[v]+=sz[u];
            calc(u);p[u]=v;gts(v,u);
            sz[v]-=sz[u];sz[u]+=sz[v];
        }
    f[u][0]=son[u];init(u);p[u]=fa;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;ans=0;
        for(int i=1,u,v;i<n;i++){
            cin>>u>>v;
            e[u].push_back(v);e[v].push_back(u);
        }
        dfs(1,0);gts(1,0);
        cout<<ans<<'\n';
        for(int i=1;i<=n;i++) e[i].clear();
    }
}

难度评分：乙中