#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long ans;
int n;
int op, clos;
string path;
vector< vector<int> > nei;
string a;
void Chain(const string& a)
{
vector< pair<int, int> > pref(a.length());
for (int i = 0; i < pref.size(); ++i)
{
pref[i].second = i;
if (a[i] == '(') ++pref[i].first;
else --pref[i].first;
if (i) pref[i].first += pref[i - 1].first;
}
vector<int> r(n, -1);
for (int i = 0; i < n; ++i)
{
int minElem = pref[i].first;
for (int j = i; j < n; ++j)
{
minElem = min(minElem, pref[j].first);
if (minElem - (i ? pref[i - 1].first : 0) < 0)
break;
else
r[i] = j;
}
}
sort(pref.begin(), pref.end());
for (int i = 0; i < n; ++i)
if (r[pref[i].second != -1)
for (int j = i; j < n && pref[j].first == (i ? pref[i - 1].first : 0); ++j)
{
if (pref[j].second <= r[pref[i].second])
++ans;
else
break;
}
}
void Dfs(int v, int par)
{
if (op == clos && a[v] == ')')
return;
if (a[v] == ')') ++clos;
else ++op;
path += a[v];
if (clos == op)
++ans;
for (int i = 0; i < nei[v].size(); ++i)
{
int to = nei[v][i];
if (to == par) continue;
Dfs(to, v);
}
path.pop_back();
if (a[v] == ')') --clos;
else --op;
}
int main()
{
cin >> n;
nei.resize(n);
cin >> a;
for (int i = 1; i < n; ++i)
{
int u, v;
cin >> u >> v; --u; --v;
nei[u].push_back(v);
nei[v].push_back(u);
}
if (false/*n <= 1000*/)
{
for (int v = 0; v < n; ++v)
{
op = clos = 0;
path = "";
Dfs(v, -1);
}
cout << ans << endl;
return 0;
}
else // Is a chain.
{
Chain(a);
reverse(a.begin(), a.end());
Chain(a);
cout << ans << endl;
char I;
cin >> I;
}
char I;
cin >> I;
}
Compilation message
zagrade.cpp: In function 'void Chain(const string&)':
zagrade.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < pref.size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp:39:29: error: expected ']' before ')' token
if (r[pref[i].second != -1)
^
zagrade.cpp: In function 'void Dfs(int, int)':
zagrade.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < nei[v].size(); ++i)
~~^~~~~~~~~~~~~~~
