import java.util.ArrayList;
import java.util.List;
public static void main
(String[] args
) { new Thread(null,
new Main
(),
"",
256 * (1L
<< 20)).
start(); }
@Override
public void run() {
int n = 500000;
List
<Integer
>[] g
= new List[n
]; for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++) {
int p = i - 1;
g[i].add(p);
g[p].add(i);
}
int result = dfs(0, -1, g);
System.
out.
println("time = " + (t2
- t1
) / 1.0e9
+ " sec, result = " + result
); }
private int dfs(int x, int p, List<Integer>[] g) {
int result = 1;
for (int y : g[x]) {
if (y == p) {
continue;
}
result += dfs(y, x, g);
}
return result;
}
}
aW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLnV0aWwuTGlzdDsKCnB1YmxpYyBjbGFzcyBNYWluIGltcGxlbWVudHMgUnVubmFibGUgewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIG5ldyBUaHJlYWQobnVsbCwgbmV3IE1haW4oKSwgIiIsIDI1NiAqICgxTCA8PCAyMCkpLnN0YXJ0KCk7CiAgICB9CgogICAgQE92ZXJyaWRlCiAgICBwdWJsaWMgdm9pZCBydW4oKSB7CiAgICAgICAgaW50IG4gPSA1MDAwMDA7CiAgICAgICAgTGlzdDxJbnRlZ2VyPltdIGcgPSBuZXcgTGlzdFtuXTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgICAgICBnW2ldID0gbmV3IEFycmF5TGlzdDw+KCk7CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgICAgIGludCBwID0gaSAtIDE7CiAgICAgICAgICAgIGdbaV0uYWRkKHApOwogICAgICAgICAgICBnW3BdLmFkZChpKTsKICAgICAgICB9CgogICAgICAgIGxvbmcgdDEgPSBTeXN0ZW0ubmFub1RpbWUoKTsKICAgICAgICBpbnQgcmVzdWx0ID0gZGZzKDAsIC0xLCBnKTsKICAgICAgICBsb25nIHQyID0gU3lzdGVtLm5hbm9UaW1lKCk7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJ0aW1lID0gIiArICh0MiAtIHQxKSAvIDEuMGU5ICsgIiBzZWMsIHJlc3VsdCA9ICIgKyByZXN1bHQpOwogICAgfQoKICAgIHByaXZhdGUgaW50IGRmcyhpbnQgeCwgaW50IHAsIExpc3Q8SW50ZWdlcj5bXSBnKSB7CiAgICAgICAgaW50IHJlc3VsdCA9IDE7CiAgICAgICAgZm9yIChpbnQgeSA6IGdbeF0pIHsKICAgICAgICAgICAgaWYgKHkgPT0gcCkgewogICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmVzdWx0ICs9IGRmcyh5LCB4LCBnKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHJlc3VsdDsKICAgIH0KfQ==