首页 > 搜索 > DFS搜索 > HDU 3804-Query on a tree-DFS-[解题报告]HOJ
2015
04-13

HDU 3804-Query on a tree-DFS-[解题报告]HOJ

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.

离线查找,蛋疼的是DFS居然要用栈….

#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];
int head[maxn], idx;
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;
nxt[idx] = head[tx]; head[tx] = idx++;
}
} 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;
stac.push(make_pair(graph.head[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.first = graph.head[y];
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);
graph.Addedge(x, y, v);
}
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
scanf("%d %d", &x, &t);
query.Addquery(x, t);
}
Solve();
for (int i = 0; i < m; i++)
{
printf("%d/n", query.ans[i]);
}
}
return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/racebug2010/article/details/6428221


, ,
  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。