Some casework: First, let’s assume n != 0:
- If k = 0, then, a=0,b=0,
- If k = 1, then, a=n,b=2*n,
- If k = 2, then, a=0,b=n,
- If k = 3, then, a=n,b=0,
For k >= 4, we can show it is not possible.
There are two phases, one where two adjacent terms have opposite signs, and one where two adjacent terms have the same sign.
For the first phase, this kind of looks like the gcd algorithm, so we can show that the absolute value of sequence is strictly decreasing for even and odd indices separately until one of them hits zero, or two adjacent terms get the same sign.
For the second phase, we can show the absolute value increases.
A number can only appear at most once in the first phase, and at most twice in the second phase.
n=0 is a special case. We can show that it can only appear at most once, or an infinite number of times.
Make sure to watch out for the case 0 0 also.
n,k = map(int, raw_input().split())
if n != 0:
x = [n,0,n,2*n]
if k == 0:
print "Yes"
print 0,0
elif 1 <= k <= 3:
print "Yes"
print x[3-k], x[4-k]
else:
print "No"
else:
if k == 0:
print "Yes"
print 1,1
elif k == 1:
print "Yes"
print 0,1
else:
print "No"
Note that the operations are reversible, so it suffices to see if the two configurations can reach any common state.
Let’s denote the canonical state to be where we merge tokens as much as possible, and after this, move the tokens to the lowest indexed nodes that they can reach. Note we can do this, since merging tokens allows us to travel across more edges. We show how we can simulate this process in O((n+m) * c) time.
For instance, we can simulate this process c times. For each token, find the set of nodes it can reach. If two tokens or more tokens can reach the same node, merge them. We only need to do this process c times since there can only be at most c merges. This process takes O(n+m) overall for all tokens (i.e. we only visit each node/edge at most once per iteration).
Thus, checking if a sequence of moves is possible is to check whether the canonical states of both the initial and final states are identical.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
RainbowRoad solver = new RainbowRoad();
int testCount = Integer.parseInt(in.next());
for (int i = 1; i <= testCount; i++)
solver.solve(i, in, out);
out.close();
}
static class RainbowRoad {
public List<RainbowRoad.Edge>[] edges;
public int[] par;
public int[] size;
public int[] mn;
public long[] ccolor;
public int n;
public int m;
public int c;
public boolean[] vis;
public void solve(int testNumber, InputReader in, OutputWriter out) {
n = in.nextInt();
m = in.nextInt();
c = in.nextInt();
edges = new List[n];
for (int i = 0; i < n; i++) edges[i] = new ArrayList<>();
for (int i = 0; i < m; i++) {
int a = in.nextInt() - 1, b = in.nextInt() - 1;
long c = in.nextLong();
edges[a].add(new RainbowRoad.Edge(a, b, c));
edges[b].add(new RainbowRoad.Edge(b, a, c));
}
int[] x = in.readIntArray(c);
int[] y = in.readIntArray(c);
for (int i = 0; i < c; i++) {
x[i]--;
y[i]--;
}
List<RainbowRoad.T> p = solve(x), q = solve(y);
out.println(p.equals(q) ? "Possible" : "Impossible");
}
public List<RainbowRoad.T> solve(int[] arr) {
par = new int[n];
size = new int[n];
mn = new int[n];
ccolor = new long[n];
for (int i = 0; i < n; i++) {
par[i] = i;
mn[i] = i;
size[i] = 1;
ccolor[i] = 0;
}
for (int j = 0; j < c; j++) {
ccolor[arr[j]] |= 1L << j;
}
for (int xx = 0; xx < c; xx++) {
vis = new boolean[n];
for (int i = 0; i < n; i++) {
if (!vis[i] && ccolor[find(i)] != 0)
dfs(i);
}
}
List<RainbowRoad.T> ret = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (find(i) == i && ccolor[i] != 0) {
ret.add(new RainbowRoad.T(mn[i], ccolor[i]));
}
}
Collections.sort(ret);
return ret;
}
public void dfs(int node) {
if (vis[node]) return;
vis[node] = true;
for (RainbowRoad.Edge next : edges[node]) {
if (join(next.a, next.b, next.c)) {
dfs(next.b);
}
}
}
public int find(int x) {
return x == par[x] ? x : (par[x] = find(par[x]));
}
public boolean join(int a, int b, long c) {
int x = find(a), y = find(b);
if (x == y) return false;
if ((ccolor[x] & c) != c && (ccolor[y] & c) != c) return false;
if (size[x] < size[y]) {
int t = x;
x = y;
y = t;
}
size[x] += size[y];
mn[x] = Math.min(mn[x], mn[y]);
par[y] = x;
ccolor[x] |= ccolor[y];
return true;
}
static class Edge {
public int a;
public int b;
public long c;
public Edge(int a, int b, long c) {
this.a = a;
this.b = b;
this.c = c;
}
}
static class T implements Comparable<RainbowRoad.T> {
public long color;
public int pos;
public T(int pos, long color) {
this.pos = pos;
this.color = color;
}
public boolean equals(Object o) {
if (!(o instanceof RainbowRoad.T)) return false;
return ((RainbowRoad.T) o).pos == pos && ((RainbowRoad.T) o).color == color;
}
public int compareTo(RainbowRoad.T other) {
return pos - other.pos;
}
public String toString() {
return pos + " " + color;
}
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int[] readIntArray(int tokens) {
int[] ret = new int[tokens];
for (int i = 0; i < tokens; i++) {
ret[i] = nextInt();
}
return ret;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public long nextLong() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
long res = 0L;
while (c >= 48 && c <= 57) {
res *= 10L;
res += (long) (c - 48);
c = this.read();
if (isSpaceChar(c)) {
return res * (long) sgn;
}
}
throw new InputMismatchException();
}
public String next() {
int c;
while (isSpaceChar(c = this.read())) {
;
}
StringBuilder result = new StringBuilder();
result.appendCodePoint(c);
while (!isSpaceChar(c = this.read())) {
result.appendCodePoint(c);
}
return result.toString();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void println(Object... objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
}
}
First, handle some special cases where the sequence doesn't start or end with '*', or contains no '*' (also, be careful when the pattern’s length is bigger than r-l+1). So, now, let's assume the sequence starts and ends with '*'.
We can proceed greedily. First, split the pattern by '*'. For each contiguous substring of letters, we can greedily take the earliest occurrence after a certain position. For each length <= 10 substring of the input, we can build a sorted vector of positions that it occurs in. The next earliest occurrence can be found using lower_bound.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
WildcardWords solver = new WildcardWords();
solver.solve(1, in, out);
out.close();
}
static class WildcardWords {
public HashMap<String, ArrayList<Integer>> mp;
public void solve(int testNumber, InputReader in, OutputWriter out) {
char[] s = in.next().toCharArray();
mp = new HashMap<>();
for (int i = 0; i < s.length; i++) {
String cur = "";
for (int j = i; j < i + 10 && j < s.length; j++) {
cur += s[j];
ArrayList<Integer> x = mp.get(cur);
if (x == null) {
mp.put(cur, x = new ArrayList<>());
}
x.add(i);
}
}
int q = in.nextInt();
while (q-- > 0) {
int l = in.nextInt() - 1, r = in.nextInt();
String w = in.next();
if (!w.contains("*")) {
if (r - l != w.length()) {
out.println("No");
continue;
}
String ee = "";
for (int i = l; i < r; i++) ee += s[i];
out.println(ee.equals(w) ? "Yes" : "No");
continue;
}
String[] pat = w.split("\\*");
int cur = l;
if (w.charAt(0) != '*') {
// must start with pat[0]
int d = getPos(pat[0], cur);
if (d != cur) {
cur = 1 << 29;
} else {
cur = d + pat[0].length();
}
}
for (int i = 1; i < pat.length; i++) {
if (pat[i].equals("")) continue;
cur = next(pat[i], cur);
}
int c = pat.length - 1;
out.println((w.charAt(w.length() - 1) == '*' ? cur <= r :
(cur <= r && getPos(pat[c], r - pat[c].length()) == r - pat[c].length())) ? "Yes" : "No");
}
}
public int next(String s, int start) {
if (start == 1 << 29) return 1 << 29;
int k = getPos(s, start);
if (k == 1 << 29) return k;
return k + s.length();
}
public int getPos(String s, int start) {
ArrayList<Integer> w = mp.get(s);
if (w == null) {
return 1 << 29;
}
int pos = Collections.binarySearch(w, start);
if (pos < 0) pos = -pos - 1;
if (pos == w.size()) {
return 1 << 29;
}
return w.get(pos);
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void println(Object... objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public String next() {
int c;
while (isSpaceChar(c = this.read())) {
;
}
StringBuilder result = new StringBuilder();
result.appendCodePoint(c);
while (!isSpaceChar(c = this.read())) {
result.appendCodePoint(c);
}
return result.toString();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
}
Just simulate the process.
Extension: solve this when n <= 10^5, |x_i|,|y_i| <= 10^5.
n = int(raw_input())
D = dict()
def go(x, y):
if not (x, y) in D:
D[(x, y)] = 0
D[(x, y)] = D[(x, y)] + 1
if D[(x, y)] == 5:
del D[(x, y)]
go(x + 1, y)
go(x, y + 1)
go(x - 1, y)
go(x, y - 1)
for i in range(n):
x, y = map(int, raw_input().split())
go(x, y)
print len(D)
First, we need to reduce it to a counting problem.
Let the sequence be a1, a2, ..., as Let's fix a prefix of the given sequence: x1, x2, ..., xp, where xi = ai for 1 ≤ i ≤ p. Now, fix xp + 1 < ap + 1, and xp + 1! = xp.
We can compute the frequency of the remaining colors. So, we want to solve this problem: How many ways are there to arrange balls of c colors with bi balls of the i-th color, such that the first ball in the line cannot be color 1.
We can solve this using dynamic programming by adding colors one by one, or inclusion exclusion.
For the inclusion exclusion solution, let's first ignore color 1.
We want to count the number of sequences where no two adjacent balls are the same color. Let's partition the sequence into "groups", where a group is a sequence of adjacent balls of the same color (not necessarily maximal).
Then, the final answer can be computed as cS - cS - 1 + cS - 2 - ....
Let's look at one color, let's say it's color j. We can precompute the number of ways to partition this into y groups. This is the number of ways to partition bj into y summands. This can be computed with a dp.
Now, let's consider compute ck. We need to assign yi groups into color i such that 
. Thus, this can be computed with a knapsack like formula. After assigning these, we can rearrange groups freely, for a total of k! ways.
Now, let's add color 1 back in. Let's fix the number of other color groups k, and also the number of groups for color 1 (call it k1). Then, instead of multiplying by (k + k0)!, we can multiply by 
.
Overall, we need to solve (sum a) * (max a) counting problems, each of which takes len(a) * max(a) * sum(a) time. The overall running time is thus 15^7 (in practice, the constant is much lower, since not all counting problems will be the maximal ones).
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
AvoidingAdjacent solver = new AvoidingAdjacent();
solver.solve(1, in, out);
out.close();
}
static class AvoidingAdjacent {
public int mod = 1000000007;
public int MAXN = 16 * 16 + 1;
public int[][] w1;
public long[] fact;
public long[] ifact;
public void solve(int testNumber, InputReader in, OutputWriter out) {
int c = in.nextInt();
int[] arr = in.readIntArray(c);
int s = AUtils.sum(arr);
int[] x = in.readIntArray(s);
for (int i = 0; i < s; i++) x[i]--;
long[][] e = Factorials.getFIF(MAXN, mod);
fact = e[0];
ifact = e[1];
w1 = new int[MAXN][MAXN];
w1[0][0] = 1;
for (int i = 1; i < MAXN; i++) {
for (int j = 1; j < MAXN; j++) {
for (int k = 1; k <= i; k++) {
w1[i][j] += w1[i - k][j - 1];
if (w1[i][j] >= mod) w1[i][j] -= mod;
}
}
}
int ans = 0;
for (int i = 0; i < s; i++) {
for (int j = 0; j < x[i]; j++) {
if (i > 0 && j == x[i - 1]) continue;
if (arr[j] > 0) {
arr[j]--;
int w = solve(arr, j);
ans += w;
if (ans >= mod) ans -= mod;
arr[j]++;
}
}
arr[x[i]]--;
}
out.println((ans + 1) % mod);
}
public int solve(int[] freq, int special) {
int d = AUtils.sum(freq);
int b = AUtils.max(freq);
if (d == 0) return 1;
if (d == freq[special]) return 0;
if (b + b - 1 > d) return 0;
int[] dp = new int[1];
dp[0] = 1;
for (int j = 0; j < freq.length; j++) {
if (freq[j] == 0 || j == special) continue;
int[] nxt = new int[dp.length + freq[j]];
for (int pgr = 0; pgr < dp.length; pgr++) {
for (int cgr = 1; cgr <= freq[j]; cgr++) {
nxt[pgr + cgr] += 1L * dp[pgr] * w1[freq[j]][cgr] % mod * ifact[cgr] % mod;
if (nxt[pgr + cgr] >= mod) nxt[pgr + cgr] -= mod;
}
}
dp = nxt;
}
int res = 0;
for (int i = 0; i < dp.length; i++) {
if (freq[special] == 0) {
long x = 1L * dp[i] * fact[i] % mod;
if ((d - i) % 2 == 0) res += x;
else res -= x;
if (res >= mod) res -= mod;
if (res < 0) res += mod;
} else {
for (int j = 1; j <= freq[special]; j++) {
long x = 1L * dp[i] * w1[freq[special]][j] % mod * ifact[j] % mod;
x = x * fact[i + j - 1] % mod * i % mod;
if ((d - i - j) % 2 == 0) res += x;
else res -= x;
if (res >= mod) res -= mod;
if (res < 0) res += mod;
}
}
}
return res;
}
}
static class AUtils {
public static int max(int[] arr) {
int res = arr[0];
for (int x : arr) res = Math.max(res, x);
return res;
}
public static int sum(int[] arr) {
int sum = 0;
for (int x : arr) {
sum += x;
}
return sum;
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void println(int i) {
writer.println(i);
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int[] readIntArray(int tokens) {
int[] ret = new int[tokens];
for (int i = 0; i < tokens; i++) {
ret[i] = nextInt();
}
return ret;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
static class Factorials {
public static long[][] getFIF(int max, int mod) {
long[] fact = new long[max];
long[] ifact = new long[max];
long[] inv = new long[max];
inv[1] = 1;
for (int i = 2; i < max; i++) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
fact[0] = 1;
ifact[0] = 1;
for (int i = 1; i < max; i++) {
fact[i] = fact[i - 1] * i % mod;
ifact[i] = ifact[i - 1] * inv[i] % mod;
}
return new long[][]{fact, ifact, inv};
}
}
}
We can look at this backwards. Consider a position for which Bob can make no more moves. Then, we have a token in every node in the tree except for the special vertex. To maximize the number of tokens that Alice can place, we can push these tokens as far away as we can from the special vertex (i.e. remove this token, and place 2 tokens on one of its children).
So, after fixing a special node, and rooting the tree at the special node, the answer is the sum over nodes of 2^d, where d is longest path from node to a leaf without going up the tree.This can be computed in O(n) time for a single node.
Now, let’s look at what happens when we move the special node to an adjacent vertex. We just need to add contribution of old vertex and subtract contribution of new vertex. These can be done if we keep track of the longest and second longest path at each node.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.List;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
TokenTree solver = new TokenTree();
solver.solve(1, in, out);
out.close();
}
static class TokenTree {
int mod = 1000000007;
int[] pow2;
List<Integer>[] graph;
int[] ans;
int[] down;
int[] up;
int[] b1;
int[] b2;
int[] id;
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.nextInt();
pow2 = new int[n + 1];
pow2[0] = 1;
for (int i = 1; i <= n; i++) {
pow2[i] = (pow2[i - 1] << 1) % mod;
}
graph = new List[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int i = 0; i < n - 1; i++) {
int a = in.nextInt() - 1, b = in.nextInt() - 1;
graph[a].add(b);
graph[b].add(a);
}
ans = new int[n];
b1 = new int[n];
b2 = new int[n];
id = new int[n];
getFarthest();
for (int i = 1; i < n; i++) {
ans[0] += pow2[down[i]];
if (ans[0] >= mod) ans[0] -= mod;
}
dfs3(0, -1);
for (int i = 0; i < n; i++) {
out.println(ans[i]);
}
}
void dfs3(int node, int par) {
for (int next : graph[node]) {
if (next == par) continue;
ans[next] = ans[node] - pow2[down[next]];
if (ans[next] < 0) ans[next] += mod;
int add = b1[node];
if (id[node] == next) add = b2[node];
ans[next] += pow2[add];
if (ans[next] >= mod) ans[next] -= mod;
dfs3(next, node);
}
}
int[] getFarthest() {
int n = graph.length;
down = new int[n];
up = new int[n];
dfs(0, -1);
dfs2(0, -1, 0);
int[] ret = new int[n];
for (int i = 0; i < n; i++) {
ret[i] = Math.max(up[i], down[i]);
}
return ret;
}
void dfs(int node, int par) {
for (int next : graph[node]) {
if (next == par) continue;
dfs(next, node);
down[node] = Math.max(down[node], down[next] + 1);
}
}
void dfs2(int node, int par, int frompar) {
up[node] = frompar;
b1[node] = up[node];
id[node] = par;
int mx1 = 0, id1 = -1, mx2 = 0;
for (int next : graph[node]) {
if (next == par) continue;
if (down[next] + 1 > b1[node]) {
b2[node] = b1[node];
b1[node] = down[next] + 1;
id[node] = next;
} else if (down[next] + 1 > b2[node]) {
b2[node] = down[next] + 1;
}
if (down[next] + 1 > mx1) {
mx2 = mx1;
mx1 = down[next] + 1;
id1 = next;
} else if (down[next] + 1 > mx2) {
mx2 = down[next] + 1;
}
}
for (int next : graph[node]) {
if (next == par) continue;
dfs2(next, node, Math.max(up[node], next == id1 ? mx2 : mx1) + 1);
}
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void println(int i) {
writer.println(i);
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
}
Lewin could you share your solution of Wildcard Words in java?
added
What is test 59 in Fibonacci Frequency?
It's
-1 1For "Avoiding Adjacent", what is the complexity of dynamic programming solution? And was it supposed to get AC?