Cod sursa(job #1207484)

Utilizator vendettaSalajan Razvan vendetta Data 13 iulie 2014 10:21:41
Problema Perb Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.66 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 250001;
const int MMAX = 400001;
const int CIFMAX = (1<<14);
int n, m;
long long  used[NMAX], t[NMAX], withoutNode[NMAX], dist[NMAX], cnt[NMAX];
long long sumStv[NMAX], sumCnt[NMAX], ans[MMAX];
vector<int> gf[NMAX];
char S[CIFMAX];
int poz;
vector< pair<int,int> > query[MMAX];
long long distInit;

void next(){
    ++poz; if (poz == CIFMAX){
        fread(S, 1, CIFMAX, stdin); poz = 0;
    }
}

void buf(int &nr){
    nr = 0;
    for(; S[poz]<'0' || S[poz]>'9'; next());
    for(; S[poz]>='0' && S[poz]<='9'; ){
        nr = nr * 10 + (S[poz] - '0');
        next();
    }
}

void dfs1(int node){
	//cout << node << "\n";
    used[node] = 1;
    int cntSon = 1;
    distInit += dist[node];
    for(int i=0; i<(int)gf[node].size(); ++i){
        int vc = gf[node][i];
        if (used[vc] == 0){
            dist[vc] = dist[node] + 1;
            t[vc] = node;
            dfs1(vc);
            cntSon += cnt[vc];
        }
    }
    cnt[node] = cntSon;
}

void dfs(int node){
	//cout << node << '\n';
    used[node] = 1;
    if (node == 1)sumStv[++sumStv[0]] = 0, sumCnt[ ++sumCnt[0] ] = 0;//, stv[++stv[0]] = 1;
    else sumStv[ ++sumStv[0] ] = dist[ node ] * 2LL * withoutNode[ node ] + sumStv[ sumStv[0]-1 ],
         sumCnt[ ++sumCnt[0] ] = sumCnt[ sumCnt[0]-1] + withoutNode[ node ];//,
         //stv[++stv[0] ] = node;
    for(int i=0; i<(int)query[node].size(); ++i){
        int difDist = (dist[node] - dist[ query[node][i].first ]-1) / 2 + (dist[node] - dist[ query[node][i].first ]-1) % 2;
        int last = sumStv[0] - difDist + 2;
        //cout << last << "\n";
        long long dif = (dist[ node ] - dist[ query[node][i].first ] - 3) - dist[node]*2;
        int dif2 = dist[node] - dist[ query[node][i].first] - 1;
        long long X = 0LL;
        if (last <= sumStv[0]) X = sumStv[ sumStv[0] ] - sumStv[ last - 1 ] +
                                                  (dif)*(sumCnt[ sumCnt[0] ] - sumCnt[ last - 1 ]);
        //cout << node << "  "<< last << " " << query[node][i].first << " "<< X << " " << cnt[node] << " " << dif << " ";
        //cout << sumStv[sumStv[0]] << " " << sumStv[ ]
        ans[ query[node][i].second ] = distInit - (X +
                                                   1ll*cnt[node]*dif2 );
    }
    for(int i=0; i<(int)gf[node].size(); ++i){
        if (used[ gf[node][i] ] == 0){
            dfs( gf[node][i] );
        }
    }
    --sumStv[0]; --sumCnt[0];
}

int main(){
    freopen("tractomarm.in", "r", stdin);
    freopen("tractomarm.out", "w", stdout);

    //cin >> n;// cout << n << "\n";
    buf(n);
    for(int i=1; i<n; ++i){
        int x=0, y=0;
        //cin >> x >> y;
        buf(x); buf(y);
        //cout << x << " " << y << "\n";
        gf[x].push_back(y);
        //cout << x << " " << y << "\n";
        gf[y].push_back(x);
        //cout << x << " " << y << "\n";
    }
	//cout << "muie";

    dfs1(1);
    for(int i=1; i<=n; ++i){
        used[i] = 0;
        if (i == 1) continue;
        withoutNode[i] = cnt[ t[i] ] - cnt[i];// cate noduri are t[i] in subarbore daca nodurile din subarb lui i nu le iau in calcul
        //cout << i << " " << withoutNode[i] << "\n";
    }
    buf(m);
    for(int i=1; i<=m; ++i){
        int x, y;
        buf(x); buf(y);
        //cout << x << " " << y << "\n";
        if (dist[x] == dist[y]) ans[i] = distInit;
        else {
            if (dist[x] > dist[y]){// x e mai jos ca y
                query[x].push_back(make_pair(y, i));
            }else query[y].push_back(make_pair(x, i));
        }
    }
    dfs(1);
    //cout << m << "\n";
    for(int i=1; i<=m; ++i){
        cout << ans[i] << "\n";
    }
}