Advertisement
Guest User

Untitled

a guest
Jan 29th, 2013
508
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.16 KB | None | 0 0
  1.     ArrayList<Long>[] a, b;
  2.     long ans = 0;
  3.     int d;
  4.     Edge[] first;
  5.  
  6.     public void solve() throws Exception {
  7.         int n = iread(), d = iread();
  8.         first = new Edge[n];
  9.         for (int i = 0; i + 1 < n; i++) {
  10.             int x = iread(), y = iread();
  11.             x--;
  12.             y--;
  13.             new Edge(x, y);
  14.             new Edge(y, x);
  15.         }
  16.         if (d % 2 != 0) {
  17.             out.write("0\n");
  18.             return;
  19.         }
  20.         this.d = d / 2;
  21.         a = new ArrayList[n];
  22.         b = new ArrayList[n];
  23.         ans = 0;
  24.         dfs(0, -1);
  25.         out.write(ans + "\n");
  26.     }
  27.  
  28.     void dfs(int x, int par) {
  29.         ArrayList<Long> firstA = new ArrayList<Long>(), firstB = new ArrayList<Long>();
  30.         firstA.add(1L);
  31.         firstB.add(0L);
  32.  
  33.         for (Edge e = first[x]; e != null; e = e.next) {
  34.             int y = e.to;
  35.             if (y == par)
  36.                 continue;
  37.             dfs(y, x);
  38.             ArrayList<Long> secondA = a[y], secondB = b[y], t = null;
  39.             //Добавляем ребро в начало поддерева соотв. дочке
  40.             secondA.add(0L);
  41.             secondB.add(0L);
  42.             //Меняем местами поддеревья, прибавлять надо большее к меньшему.
  43.             if (firstA.size() < secondA.size()) {
  44.                 t = firstA;
  45.                 firstA = secondA;
  46.                 secondA = t;
  47.                 t = firstB;
  48.                 firstB = secondB;
  49.                 secondB = t;
  50.             }
  51.             int firstL = firstA.size(), secondL = secondA.size();
  52.  
  53.             // Все индексы перевёрнуты. То есть вместо [i] используется [Len - i - 1]
  54.            
  55.             // В поддеревьях в сумме все три столицы.
  56.             for (int dist2 = 0; dist2 < secondL; dist2++) {
  57.                 int dist1 = d - dist2;
  58.                 if (dist1 >= 0 && dist1 < firstL) {
  59.                     ans += firstA.get(firstL - dist1 - 1) * secondB.get(secondL - dist2 - 1) + firstB.get(firstL - dist1 - 1)
  60.                             * secondA.get(secondL - dist2 - 1);
  61.                 }
  62.             }
  63.            
  64.             // В каждом поддереве по столице
  65.             if (secondL > d) {
  66.                 firstB.set(firstL-1, firstB.get(firstL-1) + firstA.get(firstL - d - 1) * secondA.get(secondL - d - 1));
  67.             }
  68.            
  69.             // Столица одна, в каком-то из поддеревьев
  70.             for (int dist = 0; dist < secondL; dist++) {
  71.                 firstA.set(firstL - dist - 1, firstA.get(firstL - dist - 1) + secondA.get(secondL - dist - 1));
  72.                 firstB.set(firstL - dist - 1, firstB.get(firstL - dist - 1) + secondB.get(secondL - dist - 1));
  73.             }
  74.         }
  75.  
  76.         a[x] = firstA;
  77.         b[x] = firstB;
  78.     }
  79.  
  80.     class Edge {
  81.         int from, to;
  82.         Edge next;
  83.  
  84.         public Edge(int x, int y) {
  85.             this.from = x;
  86.             this.to = y;
  87.             next = first[x];
  88.             first[x] = this;
  89.         }
  90.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement