// tree_with_file.cpp: 複擇滇��綏 錙鞭� 集蝠� 溫� 蜻瘡蝓贛蝶� 頜慣蝸粵��.
//
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
using namespace std;
const int maxsize = 40000;
vector <vector<pair<int, int>>> g;
vector <bool> used;
pair<int, int> nodes[maxsize];
int depth[maxsize];
int parent[maxsize];
int depth_bin[maxsize];
int way = 0, way_bin = 0;
int num, num_of_pairs;
int count = 0;
int nf, nt, dist;
bool run = true;
char buf [5];
ifstream fin;
void dfs (int v, int lastleng, int from);
int main()
{
fin.open("test.txt");
cout << "number of nodes: ";
fin >> buf;
num = atoi(buf);
//cout << num << endl;
g.resize(num);
//膳摘權琯� 愿 糟瘧� 滓瘩灘 � 頑瘟縊� � g
while (count != (num - 1))
{
//cout << "\nnode from: ";
fin >> buf;
nf = atoi(buf);
//cout << nf;
//cout << "node to: ";
fin >> buf;
nt = atoi(buf);
//cout << nt;
//cout << "distance: ";
fin >> buf;
dist = atoi(buf);
//cout << dist;
g[nf - 1].push_back(make_pair(nt - 1, dist));
g[nt - 1].push_back(make_pair(nf - 1, dist));
count++;
nf = nt = dist = 0;
}
//膳摘權琯� 鞣縛� 鋒� � 頑瘟縊� 隄� 鋒橢 � nodes[]
//cout << "\nnumber of pairs: ";
fin >> buf;
num_of_pairs = atoi(buf);
cout << num_of_pairs << endl;
for (int i = 0; i < num_of_pairs; i++)
{
//cout << "\nnode from: ";
fin >> buf;
nf = atoi(buf);
//cout << nf;
//cout << "node to: ";
fin >> buf;
nt = atoi(buf);
//cout << nt;
nodes[i] = make_pair(nf - 1, nt - 1);
nf = nt = 0;
}
//cout << "\n++++++++++++++++++++++++++++++++++\n";
//慚摟廓鞅飾樽粳 used
used.resize(num);
for (int i =0; i < num; i++)
{
used[i] = false;
}
//頜絹曉獵罹慚�
dfs(0, 0, 0);
//擇僮鼻錶� 擋菔靜 dfs(0, 0, 0)
/*for (int i = 0; i < num; i++)
{
cout << "depth_bin[" << i << "] = " << depth_bin[i];//幌戲慚� �粳粵錶
cout << ". depth[" << i << "] = " << depth[i];//溫慚� 餓錚 褕 蜻曆� 滇擇鈇
cout << ". parent[" << i << "] = " << parent[i] << endl;//頜窟蝌 �粳粵錶
}*/
//順鞣縛粵徹 溫慚� 餓錚 溫� 隄罩 閔窟粵磋� 鋒�
for (int i = 0; i < num_of_pairs; i++)
{
int a = nodes[i].first;
int b = nodes[i].second;
int lca = a;
int lcb = b;
while (depth_bin[a] != depth_bin[b])
{
if (depth_bin[a] > depth_bin[b])
a = parent[a];
else
b = parent[b];
}
while (a != b)
{
a = parent[a];
b = parent[b];
}
int way_ab = depth[lca] + depth[lcb] - 2 * depth[a];
cout << "Way from " << lca + 1 << " to " << lcb + 1 << " = " << way_ab << endl;
}
fin.close();
cout << "OK!";
cin.get();
return 0;
}
void dfs (int v, int lastleng, int from)
{
used[v] = true;
parent[v] = from;
depth[v] = way;
depth_bin[v] = way_bin;
for (size_t i = 0; i < g[v].size(); i++)
{
int CurrentNode = g[v][i].first;
int CurrentLen = g[v][i].second;
if (!used[CurrentNode])
{
way += CurrentLen;
way_bin++;
dfs (CurrentNode, CurrentLen, v);
}
}
way_bin--;
way -= lastleng;
}
