Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ArrayList<Long>[] a, b;
- long ans = 0;
- int d;
- Edge[] first;
- public void solve() throws Exception {
- int n = iread(), d = iread();
- first = new Edge[n];
- for (int i = 0; i + 1 < n; i++) {
- int x = iread(), y = iread();
- x--;
- y--;
- new Edge(x, y);
- new Edge(y, x);
- }
- if (d % 2 != 0) {
- out.write("0\n");
- return;
- }
- this.d = d / 2;
- a = new ArrayList[n];
- b = new ArrayList[n];
- ans = 0;
- dfs(0, -1);
- out.write(ans + "\n");
- }
- void dfs(int x, int par) {
- ArrayList<Long> firstA = new ArrayList<Long>(), firstB = new ArrayList<Long>();
- firstA.add(1L);
- firstB.add(0L);
- for (Edge e = first[x]; e != null; e = e.next) {
- int y = e.to;
- if (y == par)
- continue;
- dfs(y, x);
- ArrayList<Long> secondA = a[y], secondB = b[y], t = null;
- //Добавляем ребро в начало поддерева соотв. дочке
- secondA.add(0L);
- secondB.add(0L);
- //Меняем местами поддеревья, прибавлять надо большее к меньшему.
- if (firstA.size() < secondA.size()) {
- t = firstA;
- firstA = secondA;
- secondA = t;
- t = firstB;
- firstB = secondB;
- secondB = t;
- }
- int firstL = firstA.size(), secondL = secondA.size();
- // Все индексы перевёрнуты. То есть вместо [i] используется [Len - i - 1]
- // В поддеревьях в сумме все три столицы.
- for (int dist2 = 0; dist2 < secondL; dist2++) {
- int dist1 = d - dist2;
- if (dist1 >= 0 && dist1 < firstL) {
- ans += firstA.get(firstL - dist1 - 1) * secondB.get(secondL - dist2 - 1) + firstB.get(firstL - dist1 - 1)
- * secondA.get(secondL - dist2 - 1);
- }
- }
- // В каждом поддереве по столице
- if (secondL > d) {
- firstB.set(firstL-1, firstB.get(firstL-1) + firstA.get(firstL - d - 1) * secondA.get(secondL - d - 1));
- }
- // Столица одна, в каком-то из поддеревьев
- for (int dist = 0; dist < secondL; dist++) {
- firstA.set(firstL - dist - 1, firstA.get(firstL - dist - 1) + secondA.get(secondL - dist - 1));
- firstB.set(firstL - dist - 1, firstB.get(firstL - dist - 1) + secondB.get(secondL - dist - 1));
- }
- }
- a[x] = firstA;
- b[x] = firstB;
- }
- class Edge {
- int from, to;
- Edge next;
- public Edge(int x, int y) {
- this.from = x;
- this.to = y;
- next = first[x];
- first[x] = this;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement