首页 > maki和tree

一Wa哇一天

发表于 2020-02-04 21:19:10

题目链接：maki和tree 题目描述有一天，maki拿到了一颗树。所谓树，即没有自环、重边和回路的无向连通图。这个树有个顶点，条边。每个顶点被染成了白色或者黑色。maki想知道，取两个不同的点，它们的简单路径上有且仅有一个黑色点的取法有多少？注：①树上两点简单路径指连接两点的最短路。② 展开全文

Emcikem

发表于 2020-02-07 13:20:19

对于每一个黑色结点，定义为一棵树的根比如此时的路径有共4条＋共3条那么对于一个以B为根的树答案等于1+3 + 1*3也就是等效为而x两两相乘求会增加复杂度，所以转换为 (x表示不含黑色结点的子树的个数，n表示该黑色结点的子树棵树) #include <iostream> #includ 展开全文

SoloDance

发表于 2020-02-10 12:17:54

题目大意题目链接给你一颗n个节点的树，每个节点有黑白两种颜色，问有多少条不同的简单路径，恰好只经过一个黑点。注： 1. <u, v> 和 <v, u> 视为相同取法。2. 简单路径为两点的最短路。分析两种情况，一种是以黑点为端点，另一种黑点不为端点。展开全文

Bernard5

发表于 2020-09-12 10:36:27

使用并查集合并白色连通块从每一个黑色节点出发，查询黑色节点的每个分支的白色节点数量，再加上彼此相乘即为结果因为回头走了，每个节点都被算了两遍，所以需要cnt/2 #include <bits/stdc++.h> using namespace std; const int maxn 展开全文

Bernard5

发表于 2020-09-12 10:25:04

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; int n; ll res, dp[N][2]; char str[N]; vector<int& 展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛