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

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上的題解,好復雜,表示沒看懂

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

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


  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>
            夜夜狂射影院欧美极品| 亚洲另类自拍| 校园春色综合网| 亚洲尤物在线| 国产一区二区久久久| 久久资源在线| 欧美高清视频一区二区三区在线观看| 亚洲激情av在线| 一区二区三区日韩欧美精品| 国产精品成av人在线视午夜片| 亚洲欧美激情一区| 久久xxxx| 一本一本久久a久久精品综合麻豆| aⅴ色国产欧美| 国产一区二区高清| 亚洲成人在线视频网站| 欧美日韩国产综合新一区| 欧美在线观看一区二区| 毛片一区二区| 亚洲影院在线| 久久这里只有精品视频首页| 中文精品视频一区二区在线观看| 午夜视频在线观看一区| 美女啪啪无遮挡免费久久网站| 欧美性大战久久久久久久| 久久综合九色综合网站| 亚洲国产婷婷综合在线精品 | 国产精品福利在线观看| 久久久亚洲国产天美传媒修理工| 欧美va天堂在线| 欧美在线999| 欧美激情导航| 久久亚洲欧美| 国产精品系列在线播放| 欧美国产精品va在线观看| 国产精品久久91| 亚洲国产精品一区制服丝袜 | 久久伊人亚洲| 亚洲欧美日韩另类精品一区二区三区 | 国产欧美欧美| 欧美激情在线有限公司| 国产精品入口福利| 亚洲激情中文1区| 国产综合视频在线观看| 夜夜爽av福利精品导航 | 国产伦精品一区二区三区视频孕妇| 蜜乳av另类精品一区二区| 国产精品免费看久久久香蕉| 欧美成人午夜激情在线| 黑人中文字幕一区二区三区| 在线亚洲精品福利网址导航| 亚洲精选视频在线| 久久在线免费| 老司机精品福利视频| 国产情人综合久久777777| 一区二区三区日韩在线观看 | 亚洲伊人伊色伊影伊综合网| 日韩一区二区高清| 亚洲国产免费看| 久久精品国产亚洲a| 久久国产精品一区二区三区| 国产精品va在线播放我和闺蜜| 亚洲国产婷婷香蕉久久久久久| 亚洲二区视频在线| 久久综合国产精品台湾中文娱乐网| 久久精品72免费观看| 国产精品自拍小视频| 午夜欧美大尺度福利影院在线看| 亚洲欧美伊人| 国产精品永久在线| 香蕉久久夜色| 久久噜噜噜精品国产亚洲综合 | 欧美成人免费大片| 亚洲高清视频在线观看| 亚洲精选大片| 曰本成人黄色| 一区二区三区日韩欧美| 亚洲欧美日韩国产一区| 国产精品网站视频| 久久av资源网站| 欧美国产三区| 亚洲午夜高清视频| 国产女主播一区二区| 久久久久免费视频| 亚洲人成久久| 亚洲欧美另类在线| 国产一区二区三区在线免费观看| 久久精品亚洲一区| 亚洲高清在线播放| 亚洲欧美制服另类日韩| 国产亚洲一区二区在线观看| 久久亚洲影音av资源网| 亚洲精品一品区二品区三品区| 亚洲综合电影| 在线观看视频日韩| 欧美日韩爆操| 欧美二区不卡| 亚洲成色精品| 亚洲网站在线| 久久午夜精品| 99re6这里只有精品视频在线观看 99re6这里只有精品 | 在线观看视频一区| 欧美成人精品一区二区| 亚洲欧美大片| 欧美激情在线观看| 欧美有码在线视频| 艳妇臀荡乳欲伦亚洲一区| 国产一区二区三区最好精华液| 欧美成人精品一区二区| 西西人体一区二区| 日韩午夜高潮| 欧美顶级艳妇交换群宴| 校园激情久久| 一区二区三区黄色| 在线激情影院一区| 国产精品一区二区三区四区| 欧美激情视频一区二区三区在线播放 | 亚洲高清视频的网址| 亚洲午夜羞羞片| 在线观看一区二区精品视频| 国产精品爱啪在线线免费观看 | 亚洲老司机av| 欧美大片一区| 久久先锋资源| 久久爱www久久做| 亚洲一级黄色| 99国产精品一区| 亚洲国产精品久久久久久女王| 国产精品综合网站| 国产精品白丝黑袜喷水久久久| 久久视频精品在线| 久久www成人_看片免费不卡| 亚洲欧美怡红院| 亚洲视频日本| 夜夜嗨av一区二区三区网站四季av| 欧美激情精品久久久久久变态| 久久综合中文色婷婷| 久久久久久久尹人综合网亚洲 | 亚洲欧美精品在线观看| 一区二区三区四区五区视频| 亚洲精品色图| 夜夜爽av福利精品导航 | 亚洲欧洲日产国产网站| 亚洲福利精品| 亚洲茄子视频| 亚洲乱码国产乱码精品精98午夜| 亚洲经典三级| 亚洲精品久久久一区二区三区| 亚洲国产乱码最新视频| 在线观看日韩www视频免费 | 欧美少妇一区二区| 欧美三级午夜理伦三级中文幕| 欧美日韩午夜精品| 欧美网站在线观看| 国产精品永久| 黄色成人av网| 亚洲日韩成人| 在线亚洲美日韩| 亚洲欧美日韩国产中文| 久久精品国产清自在天天线| 久久性色av| 亚洲国产视频直播| 一区二区高清视频在线观看| 亚洲欧美日韩国产中文| 久久亚洲精品一区二区| 欧美日韩mp4| 国产自产2019最新不卡| 亚洲国产日韩欧美在线图片| 亚洲特色特黄| 久久一区二区三区四区| 亚洲国产中文字幕在线观看| 亚洲视频电影图片偷拍一区| 欧美影片第一页| 欧美精品一区二区三区很污很色的 | 欧美激情在线| 亚洲图中文字幕| 久久久久国产一区二区三区| 欧美精品国产精品日韩精品| 国产精品一区二区三区免费观看| 亚洲高清免费在线| 亚洲欧美日韩精品久久亚洲区| 巨乳诱惑日韩免费av| 亚洲色图自拍| 女人天堂亚洲aⅴ在线观看| 国产精品女主播在线观看| 亚洲国产精品成人va在线观看| 亚洲午夜精品久久| 男人的天堂亚洲在线| 亚洲午夜av在线| 欧美精品久久99久久在免费线| 国产日韩欧美成人| 亚洲私人影院在线观看| 欧美成人官网二区| 亚洲欧美精品一区| 欧美日韩精品| 亚洲欧洲一区| 免费看的黄色欧美网站| 先锋a资源在线看亚洲| 欧美日韩在线综合| 亚洲精品久久久蜜桃|