В задаче E есть еще одно классное решение. В Петрозаводске на саратовском контесте я узнал об этом приеме.
Сохраним все запросы и запустим dfs. Для каждой вершины будем хранить deque, где по h-ому индексу лежит количество потомков на глубине h (на запросы с помощью такой структуры ответить довольно легко).

Теперь главная фишка: при подсчете этой deque для текущей вершины надо не создавать новую deque, а переприсвоить ее, взяв ее от того потомка, где эта deque имеет максимальный размер (т.е. где поддерево имеет максимально возможную глубину). Именно переприсвоить, а не скопировать. Оператор '=' копирует! Т.е. надо работать с указателями.
После этого для этого потомка уже ничего нельзя посчитать — его deque испарилась — текущая вершина ее покалечила — однако все, что надо, мы уже посчитали, когда находились в этом потомке, одним dfs-ом ранее. Для остальных потомков просто пройдемся по их deque-ам и выполним что-то типа current[h+1] += child[h];

Из-за магии время работы этой штуки O(NlogN).

P.S. код: http://codeforces.net/contest/208/submission/1933305, вроде бы достаточно читабельный

Задача Е со ВКОШПА + двоичный подъем

Можете B объяснить по подробнее динамикой?

Какой ещё N^2 в 208D? Решение за чистое Θ(5N).

Контест понравился, но претесты, по задаче Б, УГ.

Хорошо, что на сервере стоит 8я вижуалка. Это помогло мне безболезненно отловить баг в коде для D, так как у себя на 10й примеры проходил, а на сервере WA#1 :-)

Здравствуйте, можно ли решить задачу 208B — Пасьянс вложенными циклами?

можете ответить что означает wrong answer 1st words differ — expected: 'ABC', found: 'ABC' http://codeforces.net/contest/208/submission/1938233

офигеть, ну объясните идиоту как делается Б. Я не пойму откуда вы 4 измерения берете!Как перекрываются подзадачи в динамике?

Честно говоря, чувствую себя совсем не в теме — что за модная структура хранения деревьев на двумерном массиве в задаче Е? Я просто делал совсем наивное хранение в двумерном массиве, а как начал чужие коды глядеть, постоянно на мифические массивы [18][10^5] натыкаюсь :) Подскажите, что за тема?

На счёт задачи 208B — пасьянс. Максималиная глубина поиска будет n. При каждом погружении появляется до 2 переходов. Выходит состояний будет O(2^n),но не O(n^4) и BFS не проидёт по времени и памяти. Вот пример моего решения через BFS, который дал RE на тесте 8:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
char a[100];
char b[100];
int head=1;
int tail=0;
bool flag=false;
struct coloda
{
    char a1;
    char a2;
    char b1;
    char b2;
    char c1;
    char c2;
    char d1;
    char d2;
    int i;
    int ost;
};
coloda j[10000000];
void BFS()
{
    while(head!=tail)
    {
        if(j[tail].ost==1)
           flag=true;
        if((j[tail].a1==j[tail].b1 || j[tail].a2==j[tail].b2) && j[tail].i>0)
        {
            j[head].a1=j[tail].a1;
            j[head].a2=j[tail].a2;
            j[head].b2=j[tail].c2;
            j[head].b1=j[tail].c1;
            j[head].c1=j[tail].d1;
            j[head].c2=j[tail].d2;
            j[head].d1=a[j[tail].i-4];
            j[head].d2=b[j[tail].i-4];
            j[head].i=j[tail].i-1;
            j[head].ost=j[tail].ost-1;
            head++;
        }
        if((j[tail].a1==j[tail].d1 || j[tail].a2==j[tail].d2) && j[tail].i>3)
        {
            j[head].a1=j[tail].b1;
            j[head].a2=j[tail].b2;
            j[head].b2=j[tail].c2;
            j[head].b1=j[tail].c1;
            j[head].c1=j[tail].a1;
            j[head].c2=j[tail].a2;
            j[head].d1=a[j[tail].i-4];
            j[head].d2=b[j[tail].i-4];
            j[head].i=j[tail].i-1;
            j[head].ost=j[tail].ost-1;
            head++;
        }
        tail++;
    }
}
int main()
{
    int n,i;
    cin>>n;
    for(i=0;i<n;i++)
       cin>>a[i]>>b[i];
    j[0].ost=n;
    j[0].i=n-1;
    j[0].a1=a[n-1];
    j[0].a2=b[n-1];
    j[0].b1=a[n-2];
    j[0].b2=b[n-2];
    j[0].c1=a[n-3];
    j[0].c2=b[n-3];
    j[0].d1=a[n-4];
    j[0].d2=b[n-4];
    BFS();
   if(flag)
      cout<<"YES"<<endl;
   else
      cout<<"NO"<<endl;
   return 0;
}

Can somebody help me for the E problem. How do I calculate the pth ancestor of some vertex. Simply climbing till the root gives TLE. The Editorial says to use the LCA algorithm. How do I use the sparse table to get the pth ancestor?

An other approach on 208E blood cousins without usage of LCA or binary search: We store the queries offline in a list on the appropriate cousin nodes and then we traverse with a dfs to update level of every node and move queries to the ancestor requested for every cousin. You can use a list to store multiple queries on every node.

A second dfs will parse and update the queries: when every node is recursively pre order processed, it pushes the count of children found on next levels (only on levels required by a query) and zero them. The dfs will continue to the children and uppon return, the final countouts would have been calculated. Previous pushed countouts are restored and updated.

O(N+M) reading O(N+M) first DFS (DFS on N nodes + move M queries to ancestor) O(N+2*M) second DFS (DFS on N nodes + push M counters, process M queries, pop M counters) O(M) print results

Overal complexity O(N+M).

Print results in order of appearance in test file and voila.

Hello, For 208E — Blood Cousins problem, could you please explain as to how a binary search helps in counting the number of nodes for the target level. I am referring to the last paragraph of the editorial "count the number of descendants of vertex u on the same height as vertex v"

Thank you in advance.

Will LCA work in E ?

LCA in E?

LCA in E?