給字串，代表一棵樹的euler tour，(代表進入一個子樹，)代表離開這個子樹，*代表來到一個葉節點。
求出這個樹的
$|s|\le 10^5$
原本以為這是噁心實作題，實際寫了才發現蓋樹的code很短。
實作上，紀錄it代表目前走到字串的哪裡，t代表接下來的節點的編號。
接下來就直接dfs就好。
複雜度$\mathcal{O}(|s|)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
signed main() { EmiliaMyWife
string s;
vector<vector<int>> edge(100001);
int it, t, mx, dep, le;
const function<void(int)> build = [&] (int u) {
if(s[it] == '*') {
it++;
return;
}
it++;
while(s[it] != ')') {
edge[u].push_back(t);
build(t++);
}
it++;
};
const function<void(int, int)> dfs = [&] (int u, int d) {
for(int v : edge[u])
dfs(v, d + 1);
mx = max<int>(mx, edge[u].size());
if(edge[u].empty())
le++;
dep = max(dep, d);
};
while(cin >> s) {
it = 0, t = 1, mx = dep = le = 0;
for(int i = 0; i < s.size(); i++)
edge[i].clear();
build(0);
dfs(0, 1);
cout << le << ' ' << dep << ' ' << mx << '\n';
}
}
|