F题dfs序题解

考虑从1为根的子树开始累加贡献，不难发现，一颗子树的贡献为从1开始的连续段的长度，而在dfs序上，以k为根，子树大小为siz[k]的子树恰好为[dfn[k],dfn[k]+siz[k]-1]的一段连续区间，所以设初始贡献为sum=1，当sum+1出现在子树中时，sum++，这样以k为根的子树贡献便统计完了，将k迭代为k的父节点，直至遍历到树根n

``` #include<bits/stdc++.h>
    #define int long long 
    #define endl '\n'
    #define pii pair<int,int>
    #define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
    using namespace std;
    const int N = 2e5 + 10;
    const double eps = 1e-6;
    const int mod = 998244353;
    const int inf = 0x3f3f3f3f;


    int h[N], e[N<<1], ne[N<<1], idx = 1;
    void add(int a, int b)
    {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    int fa[N], siz[N], cnt = 0, dfn[N];
    void dfs(int u, int f)
    {
        fa[u] = f;
        siz[u] = 1;
        dfn[u] = ++cnt;
        for (int i = h[u];i != 0;i = ne[i])
        {
            int j = e[i];
            if (j == f)continue;
            dfs(j, u);
            siz[u] += siz[j];
        }
    }
    void solve()
    {
        int n;
        cin >> n;
        for (int i = 1;i < n;i++)
        {
            int u, v;
            cin >> u >> v;
            add(u, v), add(v, u);
        }
        dfs(n, 0);
        int ans = 0, sum = 1;
        int root = 1;
        while (sum < n)
        {
            while (sum < n && dfn[sum + 1] >= dfn[root] && dfn[sum + 1] <= dfn[root] + siz[root] - 1)
            {
                sum++;
            }
            if (sum == n)break;
            ans += sum;
            root = fa[root];
        }
        cout << ans + n << endl;
    }
    signed main()
    {
        int t;
        t = 1;
        while (t--)
        {
            solve();
        }
        return 0;
    }