Pagini recente » Cod sursa (job #967085) | Cod sursa (job #2433064) | Cod sursa (job #381579) | Cod sursa (job #2836730) | Cod sursa (job #1207484)
#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";
}
}