Water Water Everywhere

3.6

14 votes
Very-Easy
Problem

Water scarcity is a major problem for Graph city. Graph city has N nodes and N - 1 edges and there is a path between every pair of nodes. Now between every pair of cities that are connected there is a pipe with capacity C.
People of Graph city wanted to test the water usage. Their metric was as follows:
Given a set of cities find the pairwise sum of flows between each pair of cities in the given set. You need to answer the above query for every test set given to you.
Flow between two cities is defined as pumping water at infinite rate from one of the selected city and measuring at how much rate water comes at the other city.
All Nodes are 1 indexed.
Input

  • The first line contains a single integer N which is the number of cities.
  • Next N-1 lines describe the edges in the tree. Each line will have 3 space separated integers where the first and the second integer specify the cities between which there exists a edge and the capacity of the flow.
  • Next line contains a single integer Q
  • Next Q line contain two lines:
    The first line has the number of nodes in the set and the next line has the space separated list of the nodes
Output
  • For each query , you need to output the pairwise sum of flow for the given set.
Constraints
  • 1 ≤ N ≤ 105
  • 1 ≤ Q ≤ 105
  • 1 ≤ C ≤ 105
  • Sum of number of nodes over all queries is less than ≤ 105

Sample Input
3
1 2 1
2 3 1
1
3
1 2 3
Sample Output
3
Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?