2015
04-13

# Query on a tree

There are some queries on a tree which has n nodes. Every query is described as two integers (X, Y).For each query, you should find the maximum weight of the edges in set E, which satisfies the following two conditions.
1) The edge must on the path from node X to node 1.
2) The edge’s weight should be lower or equal to Y.
Now give you the tree and queries. Can you find out the answer for each query?

The first line of the input is an integer T, indicating the number of test cases. For each case, the first line contains an integer n indicates the number of nodes in the tree. Then n-1 lines follows, each line contains three integers X, Y, W indicate an edge between node X and node Y whose value is W. Then one line has one integer Q indicates the number of queries. In the next Q lines, each line contains two integers X and Y as said above.

The first line of the input is an integer T, indicating the number of test cases. For each case, the first line contains an integer n indicates the number of nodes in the tree. Then n-1 lines follows, each line contains three integers X, Y, W indicate an edge between node X and node Y whose value is W. Then one line has one integer Q indicates the number of queries. In the next Q lines, each line contains two integers X and Y as said above.

1
3
1 2 7
2 3 5
4
3 10
3 7
3 6
3 4

7
7
5
-1
Hint
2<=n<=10^5
2<=Q<=10^5
1<=W,Y<=10^9
The data is guaranteed that your program will overflow if you use recursion.


#include <iostream>
#include <set>
#include <stack>
using namespace std;
const int maxn = 100005;
struct Graph
{
int pnt[maxn*2], val[maxn*2], nxt[maxn*2];
bool sign[maxn];
void Init(int n)
{
memset(head, -1, 4 * (n + 1));
memset(sign, 0, n + 1);
idx = 0;
}
void Addedge(int x, int y, int v)
{
pnt[idx] = y; val[idx] = v; nxt[idx] = head[x]; head[x] = idx++;
pnt[idx] = x; val[idx] = v; nxt[idx] = head[y]; head[y] = idx++;
}
} graph;
struct Query
{
int x[maxn], top[maxn], ans[maxn];
int nxt[maxn], head[maxn], idx;
void Init(int n)
{
memset(head, -1, 4 * (n + 1));
idx = 0;
}
void Addquery(int tx, int tt)
{
if (tx == 1) ans[idx] = -1;
x[idx] = tx; top[idx] = tt;
}
} query;
struct Node
{
int p, v;
};
multiset<int> mset;
multiset<int>::iterator it;
stack< pair<int, int> > stac;
pair<int, int> par;
void Init(int n)
{
graph.Init(n);
query.Init(n);
}
void Solve()
{
mset.insert(-1);
graph.sign[1] = 1;
while (!stac.empty())
{
par = stac.top();
stac.pop();
int &p = par.first;
if (p == -1)
{
mset.erase(mset.find(par.second));
}
else
{
int &y = graph.pnt[p];
if (!graph.sign[y])
{
graph.sign[y] = 1;
int tp = p;
p = graph.nxt[p];
stac.push(par);
par.second = graph.val[tp];
stac.push(par);
mset.insert(par.second);
for (int i = query.head[y]; i != -1; i = query.nxt[i])
{
it = mset.upper_bound(query.top[i]);
it--;
query.ans[i] = (*it);
}
}
else
{
p = graph.nxt[p];
stac.push(par);
}
}
}
}
int main()
{
int test, cas;
scanf("%d", &test);
for (cas = 1; cas <= test; cas++)
{
int n, m;
int x, y, v, t;
scanf("%d", &n);
Init(n);
for (int i = 1; i < n; i++)
{
scanf("%d %d %d", &x, &y, &v);
}
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
scanf("%d %d", &x, &t);
}
Solve();
for (int i = 0; i < m; i++)
{
printf("%d/n", query.ans[i]);
}
}
return 0;
}