每日一题4月14日 Treepath 树形dp or 思维

感觉树的题目做多了，每题都会往树形dp想。

题目大意：

给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。

思路：
第一反应是使用dfs计算每个点下面的奇数路径和偶数路径的数量。
令f[i][0/1]表示从i出发到子树的偶数路径数和奇数路劲数。
显然对于相邻的边(u,v)我们有：
f[u][0]+=f[v][1]
f[u][1]+=f[v][0]+1 //u->v是奇数边
这个我们一遍dfs可以解决。

接着我们考虑枚举每一个点x，然后答案是∑f[x][0]
但是由于我们前面处理的f[x][0]是从x出发往子树的走的，我们依然要考虑往根方向的路。
那么对于边(x,y)，我们可以进行转移：
f[y][0]+=f[x][1]-f[y][0]-1
f[y][1]+=f[x][0]-f[y][1]+1
这样子计算的话，我们会把一条边计算两边，所以最后ans/2就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,d[100040];
long long ans,f[100040][2];
vector<int>vt[100040];
void dfs(int x,int fa){
    for(int i=0;i<vt[x].size();i++){
        int y=vt[x][i];
        if(y==fa)continue;
        dfs(y,x);
        if(d[y]==1){
            f[x][0]+=0;
            f[x][1]+=1;
            continue;
        }
        f[x][0]+=f[y][1];
        f[x][1]+=f[y][0]+1;
    }

    return ;
}
void dfs2(int x,int fa){
    ans+=f[x][0];
    for(int i=0;i<vt[x].size();i++){
        int y=vt[x][i];
        if(y==fa)continue;
        f[y][0]+=f[x][1]-f[y][0]-1;
        f[y][1]+=f[x][0]-f[y][1]+1;
        dfs2(y,x);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        vt[x].push_back(y);
        vt[y].push_back(x);
        d[x]++;d[y]++;
    }
    dfs(1,-1);
    dfs2(1,-1);
    cout<<ans/2<<endl;
    return 0;
}

写完去看了眼题解，好家伙，题解也太简单了。
原来只要去计算一下奇数深度的点数量和偶数深度的点数量，然后计算就可以了。
因为奇数+奇数=偶数，偶数+偶数=偶数。
这里代码就不贴了。感觉可以作为思维题进行考查。