题目传送门
题意很好懂就是不会写(太菜了)
其实就是一简单DFS配合一点细节就好了,(为什么我总是会想到点分治?) 树上的东西还是要多练习啊 (缩点之后的图也是这样的,如果这种程度的思路都不会,我就不用混了QWQ)
废话不多说,为什么没有过了这道题?
first: 心态炸了 (赤裸裸的找借口)
second: 一想到DFS玄学的复杂度就没有细想了 (在分析复杂度上偷懒了或者说这方面的经验不足,要多分析分析才好)
嘛,正所谓 “搏一搏,单车变摩托”,不搏一下,是不可能有牌子的…
先上代码:
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 100010
#define ll long long
using namespace std;
struct node {
int to, nxt;
}edge[MAX*2];
int n;
int cnt;
int head[MAX];
int flag[MAX];
int vis[MAX];
int fa[MAX];
int num[MAX];
int k[MAX];
int sum[MAX];
void addedge(int from,int to)
{
edge[cnt] = { to,head[from] };
head[from] = cnt++;
}
int find(int x)
{
if (fa[x] != x)
fa[x] = find(fa[x]);
return fa[x];
}
void un(int a, int b)
{
int fa1 = find(a);
int fa2 = find(b);
if (fa1 != fa2)
fa[fa1] = fa2;
}
void init()
{
memset(head, -1, sizeof(head));
for (int i = 1; i <= n; i++)
fa[i] = i;
}
void dfs(int now,int father)
{
fa[now] = father;
for (int i = head[now]; i != -1; i = edge[i].nxt)
{
int to = edge[i].to;
if (flag[to] == 0 && fa[to]==to)
dfs(to, father);
}
}
ll getans(int now)
{
ll ans = 0;
int len = 1;
for (int i = head[now]; i != -1; i=edge[i].nxt)
{
int to = edge[i].to;
if (flag[to] == 0)
k[len++] = num[fa[to]];
}
for (int i = 1; i < len; i++)
sum[i] = sum[i - 1] + k[i];
ans += sum[len - 1];
for (int i = 1; i < len; i++)
{
ans += (sum[len - 1] - sum[i]) * k[i];
}
return ans;
}
int main()
{
cin >> n;
init();
string s;
cin >> s;
for (int i = 1; i <= s.size(); i++)
{
if (s[i - 1] == 'B') flag[i] = 1;
else flag[i] = 0;
}
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
addedge(a, b);
addedge(b, a);
}
for (int i = 1; i <= n; i++)
{
if (flag[i] == 0 && fa[i] == i)
{
dfs(i,i);
}
}
for (int i = 1; i <= n; i++)
{
if (flag[i]==0)
num[fa[i]]++;
}
//for (int i = 1; i <= n; i++)
//{
// cout << i << ":" << num[i] << endl;
//}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
if (flag[i] == 0) continue;
ans += getans(i);
}
cout << ans;
return 0;
}
/*
9
BBWWWWBWW
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
*/
太丑了,以后要学习一下适度压行
写这道题的时候完全没有想到连通集这玩意,经验严重不足啊,要多学习啦.
贴一个官方题解