#include #include #include using namespace std; const int MAXN = 1e5 + 5; const long long inf = 1e15 + 5; int n; vector > graph[MAXN]; int treeSize[MAXN]; long long depth[MAXN]; int order[MAXN], orderInd = 0; void DFSInit(int x, int last, long long dist) { order[x] = orderInd; depth[x] = dist; orderInd++; treeSize[x] = 1; for(pair &y: graph[x]) { if(y.first==last) continue; DFSInit(y.first, x, dist+y.second); treeSize[x] += treeSize[y.first]; } } bool isInside(int x, int y) { if(order[y]>=order[x] && order[y]<=order[x]+treeSize[x]-1) return true; return false; } long long calcDist(int x, int y, int lca) { return depth[x] + depth[y] - 2*depth[lca]; } int A, B, C; int bestNode = -1; long long minVal = inf; void DFS(int x, int last, int lcaA, int lcaB, int lcaC, long long lastVal) { if(lcaA==-1 && isInside(x, A)==false) lcaA = last; if(lcaB==-1 && isInside(x, B)==false) lcaB = last; if(lcaC==-1 && isInside(x, C)==false) lcaC = last; long long curr = calcDist(x, A, ((lcaA==-1)?x:lcaA)); curr += calcDist(x, B, ((lcaB==-1)?x:lcaB)); curr += calcDist(x, C, ((lcaC==-1)?x:lcaC)); if(curr>lastVal) return; if(minVal>curr) { minVal = curr; bestNode = x; } for(pair y: graph[x]) { if(y.first==last) continue; DFS(y.first, x, lcaA, lcaB, lcaC, curr); } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); ifstream cin("meeting.in"); ofstream cout("meeting.out"); //int n = 100000; cin >> n; for(int i = 0;i> u >> v >> val; //u = i;v = i + 1; graph[u].push_back({v, val}); graph[v].push_back({u, val}); } DFSInit(0, -1, 0); int Q = 1000; cin >> Q; while(Q--) { //A = 1;B = 25000;C = 100000; cin >> A >> B >> C; bestNode = -1; minVal = inf; DFS(0, -1, -1, -1, -1, inf); cout << bestNode << " " << minVal << '\n'; } }