結果
問題 | No.1507 Road Blocked |
ユーザー |
|
提出日時 | 2021-06-08 15:42:03 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 218 ms / 2,000 ms |
コード長 | 10,992 bytes |
コンパイル時間 | 2,369 ms |
コンパイル使用メモリ | 218,792 KB |
実行使用メモリ | 14,880 KB |
最終ジャッジ日時 | 2024-06-22 11:27:32 |
合計ジャッジ時間 | 10,020 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
// URL: https://yukicoder.me/problems/no/1507import std;version(unittest) {} elsevoid main(){int N; io.getV(N);auto g = Graph(N);foreach (_; 0..N-1) {int ui, vi; io.getV(ui, vi); --ui; --vi;g.addEdgeB(ui, vi);}auto a = SList!int(0), b = SList!int(0), visited = new bool[](N);visited[0] = true;while (!a.empty) {auto u = a.front; a.removeFront();foreach (v; g[u]) {if (!visited[v]) {a.insertFront(v);b.insertFront(v);visited[v] = true;}}}auto t = g.tree(0), c = new int[](N); c[] = 1;while (!b.empty) {auto u = b.front; b.removeFront();if (u != 0) c[t.parent[u]] += c[u];}auto r = mint(0);foreach (u; 1..N) {auto d1 = mint(c[0]), d2 = mint(c[u]), d3 = mint(c[0] - c[u]);r += (d3*(d3-1)/2 + d2*(d2-1)/2)/(d1*(d1-1)/2);}io.put(r/(N-1));}const mod = 998244353;alias mint = ModInt!mod;pure nothrow @safe{T powr(alias pred = "a*b", T, U)(const T a, U n, T one)if (isIntegral!U){auto b = T(a);alias predFun = binaryFun!pred;if (n == 0) return one;auto r = one;for (; n > 0; n >>= 1) {if (n&1) r = predFun(r, b);b = predFun(b, b);}return r;}T powr(alias pred = "a*b", T, U)(const T a, U n)if (isIntegral!U){return powr!(pred, T, U)(a, n, T(1));}}pragma(inline) pure nothrow @nogc @safe{T cdiv(T)(const T a, const T b){return (a+b-1)/b;}T pmod(T)(const T a, const T b){return a >= 0 ? a%b : a%b+b;}}pure nothrow @nogc @safe{ExtGcdResult!T extGcd(T)(const T a, const T b){if (a == 0) {return ExtGcdResult!T(T(b), T(0), T(1));} else {auto r = extGcd(b%a, a);return ExtGcdResult!T(r.gcd, r.y-(b/a)*r.x, r.x);}}private struct ExtGcdResult(T){T gcd, x, y;}}struct ModInt(int m){pragma(inline) pure nothrow @nogc @safe{this(T)(T v)if (isIntegral!T){i = nm(v);}this(ref return scope const Mint v){i = v.i;}bool opEquals(T)(T v) constif (isIntegral!T){return i == v;}bool opEquals(const Mint v) const{return i == v.i;}Mint opUnary(string op: "-")() const{return Mint(-i);}static if (m < int.max/2) {Mint opBinary(string op: "+")(int r) const{Mint m;m.i = nm(i+r);return m;}Mint opBinary(string op: "+")(const Mint r) const{Mint m;m.i = nmp(i+r.i);return m;}ref Mint opOpAssign(string op: "+")(int r){i = nm(i+r);return this;}ref Mint opOpAssign(string op: "+")(const Mint r){i = nmp(i+r.i);return this;}} else {Mint opBinary(string op: "+")(int r) const{Mint m;m.i = nm(l+r);return m;}Mint opBinary(string op: "+")(const Mint r) const{Mint m;m.i = nmp(l+r.i);return m;}ref Mint opOpAssign(string op: "+")(int r){i = nm(l+r);return this;}ref Mint opOpAssign(string op: "+")(const Mint r){i = nmp(l+r.i);return this;}}Mint opBinary(string op: "-")(int r) const{return Mint(i-r);}Mint opBinary(string op: "-")(const Mint r) const{return Mint(i-r.i);}ref Mint opOpAssign(string op: "-")(int r){i = nm(i-r);return this;}ref Mint opOpAssign(string op: "-")(const Mint r){i = nm(i-r.i);return this;}Mint opBinary(string op, T)(T r) constif ((op == "+" || op == "-") && isIntegral!T && !is(T == int)){return Mint(mixin("l"~op~"r"));}ref Mint opOpAssign(string op, T)(T r)if ((op == "+" || op == "-") && isIntegral!T && !is(T == int)){i = nm(mixin("l"~op~"r"));return this;}Mint opBinary(string op: "*", T)(T r) constif (isIntegral!T){Mint m;m.i = nm(l*r);return m;}Mint opBinary(string op: "*")(const Mint r) const{Mint m;m.i = nmp(l*r.i);return m;}ref Mint opOpAssign(string op: "*", T)(T r)if (isIntegral!T){i = nm(l*r);return this;}ref Mint opOpAssign(string op: "*")(const Mint r){i = nmp(l*r.i);return this;}ref Mint opUnary(string op: "++")(){i = nmp(i+1);return this;}ref Mint opUnary(string op: "--")(){i = nm(i-1);return this;}Mint opBinary(string op: "^^", T)(T n)if (isIntegral!T){return powr(this, n, Mint(1));}Mint opBinary(string op: "/")(const Mint r) const{return Mint(l*r.inv.i);}ref Mint opOpAssign(string op: "/")(const Mint r){i = nm(l*r.inv.i);return this;}Mint opBinary(string op: "/", T)(T r) constif (isIntegral!T){return opBinary!op(Mint(r));}ref Mint opOpAssign(string op: "/", T)(T r)if (isIntegral!T){return opOpAssign!op(Mint(r));}Mint inv() const{return Mint(extGcd(i, m).x);}}pure nothrow @nogc @safe{ref Mint opAssign(T)(T v)if (isIntegral!T){i = nm(v);return this;}ref Mint opAssign(const Mint v){i = v.i;return this;}}pure nothrow @safe{string toString() const{return i.to!string;}}private{alias Mint = ModInt!m;version(BigEndian) union { long l; struct { int i2; int i; } }else union { long l; int i; }pragma(inline) pure nothrow @nogc @safe{int nm(T)(T v) constif (isIntegral!T){return cast(int)pmod(v, m);}int nmp(T)(T v) constif (isIntegral!T){return cast(int)(v%m);}}}}struct Graph{alias Node = int;Node n;Node[][] g;alias g this;pure nothrow @safe{this(Node n){this.n = n;g = new Node[][](n);}void addEdge(Node u, Node v)in { assert(0 <= u && u < n && 0 <= v && v < n); }do{g[u] ~= v;}void addEdgeB(Node u, Node v)in { assert(0 <= u && u < n && 0 <= v && v < n); }do{g[u] ~= v;g[v] ~= u;}}}struct GraphW(W = int, W i = 10^^9){alias Node = int, Wt = W, inf = i;struct Edge{Node src, dst;Wt wt;alias cap = wt;}Node n;Edge[][] g;alias g this;pure nothrow @safe{this(Node n){this.n = n;g = new Edge[][](n);}void addEdge(Node u, Node v, Wt w)in { assert(0 <= u && u < n && 0 <= v && v < n); }do{g[u] ~= Edge(u, v, w);}void addEdgeB(Node u, Node v, Wt w)in { assert(0 <= u && u < n && 0 <= v && v < n); }do{g[u] ~= Edge(u, v, w);g[v] ~= Edge(v, u, w);}}}struct GraphM(W = int, W i = 10^^9){alias Node = int, Wt = W, inf = i;Node n;Wt[][] g;alias g this;pure nothrow @safe{this(int n){this.n = n;g = new Wt[][](n, n);}static GraphM!(W, i) init(Node n){auto g = GraphM!(W, i)(n);foreach (i; 0..n) { g[i][] = inf; g[i][i] = 0; }return g;}}}struct Tree(Graph){alias Node = Graph.Node;Graph g;alias g this;Node root;Node[] parent, dfsOrder;int[] size, depth;pure nothrow @safe{this(Graph g, Node r)in { assert(0 <= r && r < g.n); }do{this.g = g;this.root = r;parent = new Node[](n);depth = new int[](n);depth[] = -1;auto st = SList!UP(UP(r, r));while (!st.empty) {auto up = st.front; st.removeFront();parent[up.u] = up.p;depth[up.u] = depth[up.p] + 1;dfsOrder ~= up.u;foreach (v; g[up.u])if (v != up.p) st.insertFront(UP(v, up.u));}size = new int[](n);size[] = 1;foreach_reverse (u; dfsOrder.drop(1))size[parent[u]] += size[u];}auto children(Node u) constin { assert(0 <= u && u < g.n); }do{return g[u].filter!(v => v != parent[u]);}}private{struct UP { Node u, p; }}}pure nothrow @safe{auto tree(Graph, Node)(Graph g, Node r)in { assert(0 <= r && r < g.n); }do{return Tree!Graph(g, r);}}auto io = IO!()();struct IO(alias IN = stdin, alias OUT = stdout){import core.stdc.stdlib : exit;void getV(T...)(ref T v){foreach (ref w; v) get(w);}void getA(T)(size_t n, ref T v)if (hasAssignableElements!T){v = new T(n);foreach (ref w; v) get(w);}void getC(T...)(size_t n, ref T v)if (allSatisfy!(hasAssignableElements, T)){foreach (ref w; v) w = new typeof(w)(n);foreach (i; 0..n) foreach (ref w; v) get(w[i]);}void getM(T)(size_t r, size_t c, ref T v)if (hasAssignableElements!T && hasAssignableElements!(ElementType!T)){v = new T(r);foreach (ref w; v) getA(c, w);}template getS(E...){void getS(T)(size_t n, ref T v){v = new T(n);foreach (ref w; v) foreach (e; E) mixin("get(w."~e~");");}}const struct PutConf{bool newline = true, flush, exit;string floatFormat = "%.10f", delimiter = " ";}void put(alias conf = "{}", T...)(T v){putMain!conf(v);}void putB(alias conf = "{}", S, T)(bool c, S t, T f){if (c) put!conf(t);else put!conf(f);}void putRaw(T...)(T v){OUT.write(v);OUT.writeln;}private{dchar[] buf;auto sp = (new dchar[](0)).splitter;void nextLine(){IN.readln(buf);sp = buf.splitter;}void get(T)(ref T v){if (sp.empty) nextLine();v = sp.front.to!T;sp.popFront();}void putMain(alias conf, T...)(T v){mixin("const PutConf c = "~conf~";");foreach (i, w; v) {putOne!conf(w);if (i+1 < v.length) OUT.write(c.delimiter);}static if (c.newline) OUT.writeln;static if (c.flush) OUT.flush();static if (c.exit) exit(0);}void putOne(alias conf, T)(T v){mixin("const PutConf c = "~conf~";");static if (isInputRange!T && !isSomeString!T) putRange!conf(v);else static if (isFloatingPoint!T) OUT.write(format(c.floatFormat, v));else static if (hasMember!(T, "fprint")) v.fprint(OUT);else OUT.write(v);}void putRange(alias conf, T)(T v){mixin("const PutConf c = "~conf~";");auto w = v;while (!w.empty) {putOne!conf(w.front); w.popFront();if (!w.empty) OUT.write(c.delimiter);}}}}