#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N;
ll sol;
string S;
int PREF[300096];
int SUFF[300096];
bool V[300096];
int SIZE[300096];
vector <int> VG[300096];
char *pos, BUFFER[5000096];
inline int getnum()
{
char C;
while ((C = *pos++) < '0');
int RET = C -= '0';
while ((C = *pos++) >= '0') RET = 10 * RET + C - '0';
return RET;
}
inline void SDFS(int node, queue <pair <int, int>> &Q, int parent = 0)
{
SIZE[node] = 1;
Q.push({parent, node});
for(int x : VG[node])
{
if(V[x] || (x == parent)) continue;
SDFS(x, Q, node);
SIZE[node] += SIZE[x];
}
return;
}
inline int GetCentroid(int node)
{
int RET = 0, best = INT_MAX, temp;
queue <pair <int, int>> Q;
SDFS(node, Q);
while(Q.size())
{
temp = SIZE[node] - SIZE[Q.front().second];
for(int x : VG[Q.front().second]) if((!V[x]) && (x != Q.front().first)) temp = max(SIZE[x], temp);
if(temp < best) {RET = Q.front().second; best = temp;}
Q.pop();
}
return RET;
}
inline void DFS1(int node, char c, int &depth, pair <int, int> pref, pair <int, int> suff, int parent = 0)
{
if(S[node - 1] == '(')
{
suff.first++;
pref.first += !pref.second;
pref.second -= bool(pref.second);
}
else
{
pref.second++;
suff.second += !suff.first;
suff.first -= bool(suff.first);
}
sol += (!suff.first) * PREF[suff.second - (c == ')') + (c == '(')] + (!pref.second) * SUFF[pref.first - (c == '(') + (c == ')')];
for(int x : VG[node]) if((!V[x]) && (x != parent)) DFS1(x, c, depth, pref, suff, node);
return;
}
inline void DFS2(int node, char c, int &depth, pair <int, int> pref, pair <int, int> suff, int parent = 0)
{
if(S[node - 1] == '(')
{
suff.first++;
pref.first += !pref.second;
pref.second -= bool(pref.second);
}
else
{
pref.second++;
suff.second += !suff.first;
suff.first -= bool(suff.first);
}
SUFF[suff.second] += !suff.first;
PREF[pref.first] += !pref.second;
depth = max({pref.first, suff.second, depth});
for(int x : VG[node]) if((!V[x]) && (x != parent)) DFS2(x, c, depth, pref, suff, node);
return;
}
inline void CD()
{
int centroid;
queue <int> Q;
Q.push(1);
while(Q.size())
{
centroid = GetCentroid(Q.front());
V[centroid] = true;
char c = S[centroid - 1];
PREF[1] = c == '(';
SUFF[1] = c == ')';
int depth = 0;
for(int x : VG[centroid])
{
if(V[x]) continue;
DFS1(x, c, depth, {c == '(', c == ')'}, {c == '(', c == ')'});
DFS2(x, c, depth, {c == '(', c == ')'}, {c == '(', c == ')'});
Q.push(x);
}
for(; depth + 1; depth--) PREF[depth] = SUFF[depth] = 0;
Q.pop();
}
return;
}
int main()
{
fread(pos = BUFFER, 1, 5000000, stdin);
N = getnum();
while((*pos != '(') && (*pos != ')')) pos++;
for(int i = 1; i <= N; i++) S.push_back(*pos++);
int u, v;
for(int i = 1; i < N; i++)
{
u = getnum();
v = getnum();
VG[u].push_back(v);
VG[v].push_back(u);
}
CD();
cout << sol << '\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
zagrade.cpp: In function 'int main()':
zagrade.cpp:112:8: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | fread(pos = BUFFER, 1, 5000000, stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |