青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

此 blog 已棄。

Query on a tree, ACM-DIY Group Contest 2011 Spring 之 5,HDOJ 3804

Query on a tree

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description
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?
 

Input
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.
 

Output
For each test case, you should output Q lines. If no edge satisfy the conditions described above,just output “-1” for this query. Otherwise output the answer for this query.
 

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

Sample Output
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.
 

Source
ACM-DIY Group Contest 2011 Spring


OJ上的題解,好復(fù)雜,表示沒看懂

這個解法好簡單,謝謝 Topsky 的指點,表示 YM

手寫棧 DFS 樹中的每個點,用 map 記錄當前訪問的點到根節(jié)點的所有權(quán)值,用 map 的 upper_bound 求得當前訪問點上的所有詢問的結(jié)果,DFS 結(jié)束后一起輸出結(jié)果。


  1 #include <iostream>
  2 #include <cstdio>
  3 #include <map>
  4 #include <list>
  5 #include <stack>
  6 #include <cstring>
  7 #include <algorithm>
  8 
  9 using namespace std;
 10 
 11 const int N = 100009;
 12 const int Q = 100009;
 13 
 14 typedef  pair< intint > PII;
 15 typedef  list< PII > LPII;
 16 typedef  LPII::iterator  LPII_I;
 17 typedef  pair< int, LPII_I > SD;
 18 typedef  stack< SD >  STACK;
 19 typedef  map< intint > MII;
 20 typedef  MII::iterator  MII_I;
 21 
 22 int q;
 23 LPII qry[ N ]; //  y, id
 24 int ans[ Q ];
 25 
 26 int n, wf[ N ];
 27 LPII adj[ N ]; // node, weight
 28 
 29 void input() {
 30         int i, u, v, w;
 31         scanf( "%d"&n );
 32         for ( i = 1; i <= n; ++i ) {
 33                 adj[ i ].clear();
 34                 qry[ i ].clear();
 35         }
 36         for ( i = 1; i < n; ++i ) {
 37                 scanf( "%d%d%d"&u, &v, &w );
 38                 adj[ u ].push_back( PII(v,w) );
 39                 adj[ v ].push_back( PII(u,w) );
 40         }
 41         scanf( "%d"&q );
 42         for ( i = 1; i <= q; ++i ) {
 43                 scanf( "%d%d"&u, &v );
 44                 qry[ u ].push_back( PII(v,i) );
 45         }
 46 }
 47 
 48 void solve() {
 49         static int ink[ N ];
 50         SD sd;
 51         STACK stk;
 52         MII   con;
 53         LPII_I   ite;
 54         
 55         sd.first = 1;
 56         sd.second = adj[ 1 ].begin();
 57         stk.push( sd );
 58         memset( ink, 0sizeof(ink) );
 59         ink[ 1 ] = 1;
 60         con[ -1 ] = 1;
 61         wf[ 1 ] = -1;
 62         for ( ite = qry[ 1 ].begin(); ite != qry[ 1 ].end(); ++ite ) {
 63                 ans[ ite->second ] = -1;
 64         }
 65         while ( ! stk.empty() ) {
 66                 sd = stk.top();
 67                 stk.pop();
 68                 if ( sd.second == adj[ sd.first ].end() ) {
 69                         if ( --con[ wf[ sd.first ] ] < 1 ) {
 70                                 con.erase( wf[ sd.first ] );
 71                         }
 72                 }
 73                 else {
 74                         int j = sd.second->first;
 75                         int w = sd.second->second;
 76                         if ( ink[ j ] ) {
 77                                 ++(sd.second);
 78                                 stk.push( sd );
 79                         }
 80                         else {
 81                                 ink[ j ] = 1;
 82                                 wf[ j ] = w;
 83                                 ++(con[ w ]);
 84                                 for ( ite = qry[ j ].begin(); ite != qry[ j ].end(); ++ite ) {
 85                                         MII_I  mit = con.upper_bound( ite->first );
 86                                         --mit;
 87                                         ans[ ite->second ] = mit->first;
 88                                 }
 89                                 ++(sd.second);
 90                                 stk.push( sd );
 91                                 sd.first = j;
 92                                 sd.second = adj[ j ].begin();
 93                                 stk.push( sd );
 94                         }
 95                 }
 96         }
 97 }
 98 
 99 void output() {
100         for ( int i = 1; i <= q; ++i ) {
101                 printf( "%d\n", ans[ i ] );
102         }
103 }
104 
105 int main() {
106         int td, i, u, v, w;
107         scanf( "%d"&td );
108         while ( td-- > 0 ) {
109                 input();
110                 solve();
111                 output();
112         }
113         return 0;
114 }
115 


posted on 2011-03-26 20:32 coreBugZJ 閱讀(1096) 評論(0)  編輯 收藏 引用 所屬分類: ACM

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            午夜精品久久久久久久白皮肤| 亚洲午夜激情| 久久蜜桃精品| 好吊视频一区二区三区四区| 久久福利电影| 久久久久久综合网天天| 亚洲国产影院| 日韩视频精品在线观看| 欧美日韩黄色大片| 性欧美精品高清| 欧美资源在线| 亚洲视频福利| 亚洲一区二区视频| 好吊日精品视频| 亚洲国产日韩欧美| 欧美精品久久99| 欧美诱惑福利视频| 久久久久久久久伊人| 99精品免费| 欧美在线观看你懂的| 午夜激情久久久| 国产精品v日韩精品v欧美精品网站| 一区二区高清在线观看| 欧美日韩国产va另类| 亚洲欧洲精品一区二区精品久久久 | 香蕉免费一区二区三区在线观看| 欧美日韩免费看| 日韩亚洲视频| 久久精品卡一| 久久精品视频导航| 在线不卡欧美| 亚洲国产精品成人久久综合一区| 亚洲色图在线视频| 噜噜噜躁狠狠躁狠狠精品视频| 最近中文字幕日韩精品| 日韩亚洲欧美综合| 国产精品亚洲综合色区韩国| 久久久久欧美精品| 欧美不卡在线视频| 亚洲一区二区三区激情| 亚洲一区二区三区四区五区午夜| 国产欧美一区二区三区久久| 久久精品亚洲精品| 男男成人高潮片免费网站| 日韩亚洲精品在线| 久久视频国产精品免费视频在线| 久久久噜噜噜久久中文字免| 国产亚洲人成a一在线v站| 久久精品国产一区二区三区免费看| 久久精品国产亚洲一区二区| 亚洲国产视频一区| 一区二区国产在线观看| 国产欧美日韩一区| 欧美激情一区二区三级高清视频| 欧美日韩国产成人高清视频| 亚洲韩国日本中文字幕| 亚洲国产一区二区a毛片| 媚黑女一区二区| 亚洲福利在线看| 亚洲国产精品123| 欧美精品v国产精品v日韩精品 | 麻豆国产va免费精品高清在线| 欧美电影电视剧在线观看| 午夜精品一区二区三区电影天堂 | 看片网站欧美日韩| 亚洲激情视频在线观看| 99精品国产一区二区青青牛奶| 亚洲欧美一区二区激情| 亚洲国产精品悠悠久久琪琪| 欧美激情久久久| 欧美天天在线| 久久久久99精品国产片| 国产亚洲精品一区二555| 亚洲欧洲在线视频| …久久精品99久久香蕉国产| 亚洲天堂av在线免费| 91久久久久久久久久久久久| 久久成人精品视频| 欧美夜福利tv在线| 欧美专区第一页| 亚洲欧美日韩国产另类专区| 欧美大片在线观看| 欧美暴力喷水在线| 黑人极品videos精品欧美裸| 在线中文字幕一区| 日韩视频在线观看免费| 老色鬼精品视频在线观看播放| 午夜在线播放视频欧美| 欧美视频一区二区在线观看 | 欧美一区国产二区| 国产一区二区中文字幕免费看| 亚洲精品欧美| 国产日韩欧美电影在线观看| 亚洲欧洲日本专区| 国产精品观看| 在线一区二区日韩| 亚洲激情二区| 久久久久久久精| 午夜精品一区二区三区在线 | 免费91麻豆精品国产自产在线观看| 国产日韩欧美麻豆| 午夜影视日本亚洲欧洲精品| 久久精品国产精品亚洲精品| 国产欧美在线播放| 欧美在线观看一区| 亚洲国产小视频在线观看| 亚洲免费成人av| 亚洲黄色影院| 欧美视频在线观看一区| 亚洲一区在线观看免费观看电影高清| 亚洲欧美日韩在线高清直播| 欧美77777| 久久国产一区二区| 在线看片成人| 欧美风情在线| 99国内精品| 久久国产精品黑丝| 国模精品一区二区三区| 久久久久成人精品| 91久久精品一区二区别| 亚洲免费伊人电影在线观看av| 国产精品萝li| 久久精品国产在热久久| 亚洲国产精品成人精品| 亚洲女同在线| 在线观看精品视频| 欧美日韩三区四区| 久久精品国产久精国产爱| 亚洲卡通欧美制服中文| 欧美高清视频在线| 亚洲精品欧美一区二区三区| 亚洲最新在线| 欧美日韩在线免费观看| 久久精品五月| 久久综合久久综合这里只有精品| 一区二区三区成人精品| 久久精品久久综合| 一本色道久久综合亚洲精品按摩| 国产日韩亚洲欧美综合| 欧美不卡激情三级在线观看| 亚洲午夜精品久久| 亚洲第一福利视频| 亚洲深夜福利视频| 亚洲国产精品久久久久婷婷884| 欧美日韩三级在线| 久久躁狠狠躁夜夜爽| 亚洲免费中文字幕| 亚洲精品欧美日韩专区| 欧美在线观看天堂一区二区三区| 亚洲精品在线观看免费| 激情综合久久| 国产精品视频一| 欧美人与禽性xxxxx杂性| 久久婷婷激情| 亚洲欧美网站| 免费观看一区| 亚洲图片你懂的| 国产精品99久久久久久www| 亚洲电影激情视频网站| 国产日韩亚洲欧美综合| 国产精品久久久久久av福利软件| 欧美电影在线观看完整版| 午夜精品视频在线观看| 亚洲免费电影在线观看| 亚洲国产婷婷| 欧美成人自拍| 欧美好吊妞视频| 欧美v国产在线一区二区三区| 久久久久国产精品一区二区| 欧美亚洲网站| 亚洲一区二区不卡免费| 9l视频自拍蝌蚪9l视频成人| 在线视频国内自拍亚洲视频| 国产亚洲精品aa| 国产女主播一区二区| 欧美午夜视频| 一本色道久久88精品综合| 欧美成人在线免费视频| 美女视频黄a大片欧美| 久久久久久久久久久久久久一区| 久久精品99久久香蕉国产色戒| 午夜精品久久久久久久| 欧美在线中文字幕| 久久久久久噜噜噜久久久精品| 久久精品国产91精品亚洲| 久久久99精品免费观看不卡| 久久乐国产精品| 女女同性女同一区二区三区91| 久久蜜桃香蕉精品一区二区三区| 亚洲激情校园春色| 久久久久久穴| 久久九九精品| 久久蜜桃av一区精品变态类天堂| 男男成人高潮片免费网站| 欧美日本国产精品| 国产欧美三级| 亚洲第一成人在线| 9色精品在线| 香港久久久电影| 欧美成人免费网站|