打码网站怎么做接口,网络搭建国赛题,网站开发需要什么证书,公司网站主要几方面文章目录题目描述题解#xff1a;代码#xff1a;传送时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K 64bit IO Format: %lld 题目描述 给定一棵n个点的树#xff0c;问其中有多少条长度为偶数的路径。路径…
文章目录题目描述题解代码传送时间限制C/C 1秒其他语言2秒 空间限制C/C 32768K其他语言65536K 64bit IO Format: %lld 题目描述 给定一棵n个点的树问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。 输入描述: 第一行一个数n表示点的个数 接下来n-1行每行两个整数xy表示边 保证输入数据形成一棵树 1n100000 输出描述: 一行一个整数表示答案。 示例1 输入
3
1 2
1 3输出
1题解
求长度为偶数的路径 偶数层的点到偶数层的点长度是偶数 奇数层到奇数层的点的路径长度也是偶数 奇数层的点到偶数层的点路径长度就算奇数 所以需要统计多少个奇数层多少点偶数层多少点 我们发现如果层数奇偶性一样路径长度就是偶数 为什么呢引用邓老师的讲解 我们可以考虑先让两个点里深度深的那个往上走走到和另外一个点一样的高度这个显然是偶数步完成的之后两个点一起往上走直到汇合走到步数是一样的所以最终加起来也是偶数。 然后我们会用到数组dp[][] dp[i][0/1]表示以i为根的子树与根节点i的距离 因为距离长度只有偶数奇数两种情况所以我们把偶数设为0奇数设为1这样好统计 u是v的父亲 也就是一个来自v的子树的点到u点的路径会比到v的路径长度 长1 这样我们有 dp[u][0]dp[v][1] 以u为根的子树与u的距离长度为偶数的情况一个本身另一个来自dp[v][i].因为以v为根节点与v的距离为奇数那到u的距离就要加1也就是偶数 dp[u][1]dp[v][0] 同理
sum dp [ u ] [ 0 ] * dp [ v ] [ 1 ] dp [ u] [ 1 ] * dp [ v ] [ 0 ] 已有dp[u][0]条以u为端点长度为偶数的路径与dp[v][1]条以v为端点长度为奇数的路径合并可以得到 dp [ u ] [ 0 ] * dp [ v ] [ 1 ] 条长度为偶数的路径 同理dp[u][i]*dp[v][0]也是一样
代码
#pragma GCC optimize(2)
#includebits/stdc.h
typedef long long ll;
const int maxn1e52;
using namespace std;
ll dp[maxn][3];
ll sum0;
vectorint edge[maxn];
void dfs(int u,int fa)
{dp[u][0]1;for (int v : edge[u]) {if(vfa)continue;dfs(v,u);sumdp[u][0]*dp[v][1]dp[u][1]*dp[v][0];dp[u][0]dp[v][1];dp[u][1]dp[v][0];}
}
int main()
{int n;scanf(%d,n);int a,b;for(int i1;in;i){cinab;edge[a].push_back(b);edge[b].push_back(a);}dfs(1,0);coutsum;
}
