#include #include #include using namespace std; #define SOUBOR_VSTUP "doprava.in" #define MAX_N 1000000 #define MAX_LOGN 20 /*Tvar vstupu: Na prvním řádku počet zastávek (N), na následujících N-1 řádcích popisy spojů mezi nimi (strom na N vrcholech má právě N-1 hran) ve tvaru: "zastávka1 zastávka2 počet_cestujících" (zastávky mají čísla 1..N) Na dalším řádku K a poté K řádků dotazů ve tvaru "odkud kam" */ //Struktura pro sousedy a strom typedef struct tsoused { int vrchol; int cestujici; } tsoused; vector sousedi[MAX_N]; int hloubka[MAX_N]; //Struktura pro zpětné odkazy a pro maxima jimi pokrytá //[vrchol][K] je odkaz zpět o 2^K (pro K=0 je to otec) int zpetny_odkaz[MAX_N][MAX_LOGN]; int zpetny_odkaz_max[MAX_N][MAX_LOGN]; void vytvor_zpetne_odkazy(int vrchol) { int j=1; while(zpetny_odkaz[vrchol][j-1]!=-1 && zpetny_odkaz[zpetny_odkaz[vrchol][j-1]][j-1]!=-1) { //Zpětný odkaz o j je dvakrát zpětný odkaz o j-1 zpetny_odkaz[vrchol][j]=zpetny_odkaz[zpetny_odkaz[vrchol][j-1]][j-1]; zpetny_odkaz_max[vrchol][j]=max(zpetny_odkaz_max[vrchol][j-1],zpetny_odkaz_max[zpetny_odkaz[vrchol][j-1]][j-1]); j++; } } void DFS(int vrchol, int nastav_hloubka, int otec, int cestujici_od_otce) { hloubka[vrchol]=nastav_hloubka; zpetny_odkaz[vrchol][0]=otec; zpetny_odkaz_max[vrchol][0]=cestujici_od_otce; vytvor_zpetne_odkazy(vrchol); //Rekurzivně se zavoláme na všechny sousedy (tedy ve stromě potomky), //ty již mohou využívat spočtené zpětné odkazy tohoto vrcholu for(int i=0;i=0;j--) { //Pomocí bitového posunu zde spočítáme, o kolik úrovní výše nás zpětný //odkaz posune (2^K je totiž 1 posunutá v bitovém zápise o K míst doleva) if(hloubka[a]-(1<=hloubka[b]) { maximum=max(maximum,zpetny_odkaz_max[a][j]); a=zpetny_odkaz[a][j]; } } //Hloubky vyrovnané, postupujeme společne ke společnému předchůdci for(int j=MAX_LOGN;j>=0;j--) { if(hloubka[a]-(1<=0 && (zpetny_odkaz[a][j]!=zpetny_odkaz[b][j] || j==0)) { maximum=max(maximum,zpetny_odkaz_max[a][j]); maximum=max(maximum,zpetny_odkaz_max[b][j]); a=zpetny_odkaz[a][j]; b=zpetny_odkaz[b][j]; } } return maximum; } int main() { FILE *vstup=fopen(SOUBOR_VSTUP, "r"); int N; fscanf(vstup,"%d",&N); for(int i=0;i