[比赛][TreeDP][树的性质][换轴][统计技巧] codeforces 1060E Sergey and Subway

自己思路的问题：每次用一个中转节点多连一条线就是等于跳过了一个节点，想到了偶数就是/2，奇数是+1/2，但是没有想到怎么去统计实现。

这个问题最后的答案可以表示为（S+O)/2，其中S是所有点对之间的路径长度之和，O是路径长度为奇数的路径的数量。然后就是如何计算这两个数字的问题。

我以前的理解是求S得用两遍dfs的treeDP，然而这次学到了新操作就是可以分别考察每一条边他被多少对点之间的路径包含了，只需要求出有根树每个点对应的子树中的节点个数即可，S+=(n-subts[x])*subs[x]。

求O的方法就更妙了，画出来一颗有根树就可以发现，两个节点之间的距离奇偶性可以用他们到根节点的奇偶性来表示！（因为树形结构本身对于根节点来说有某种意义上的差分性质emmm），假如两个点到root的路径长度（也就是depth）奇偶性相同，那么他们之间的路径就是偶数的否则是奇的。所以只需要求出来所有的奇数层的节点个数乘以所有的偶数层的节点个数就可以得到O了。

#include
//#include
//#include

using namespace std;

typedef long long LL;
const int maxn=2e5+5;
const int mod=1e9+7;

vector G[maxn];
LL subs[maxn];
LL no,ne;

void dp(int x,int fa,int depth)
{
    if(depth&1)
        no++;
    else
        ne++;
    int len=G[x].size();
    subs[x]++;
    for (int i=0;i>n;
    for (int i=1; i>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dp(u,-1,0);
    LL s=0;
    for (int i=1;i<=n;i++)
        s+=subs[i]*(n-subs[i]);
    cout<<(s+no*ne)/2<