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

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一区二区三区在线观看| 国产亚洲永久域名| 亚洲国产aⅴ天堂久久| 欧美国产综合视频| 校园春色国产精品| 久久亚洲精品伦理| 在线一区欧美| 欧美资源在线| 亚洲国产裸拍裸体视频在线观看乱了中文 | 欧美精品免费视频| 亚洲专区在线| 久久精品99国产精品日本| 亚洲黄页一区| 亚洲欧美激情四射在线日 | 久久美女性网| 欧美精品在线网站| 久久九九精品99国产精品| 欧美成人69| 久久精品免费播放| 欧美日本一区二区高清播放视频| 香蕉视频成人在线观看| 欧美不卡在线| 久久精品噜噜噜成人av农村| 欧美激情区在线播放| 久久精品国产综合精品| 欧美日韩人人澡狠狠躁视频| 鲁大师影院一区二区三区| 国产精品久久久久久久久久久久久 | 亚洲毛片在线| 在线不卡中文字幕| 亚洲校园激情| 日韩视频中午一区| 久久理论片午夜琪琪电影网| 午夜精品在线观看| 欧美日韩一区二区三区| 欧美高清视频一区| 国产在线成人| 亚洲综合清纯丝袜自拍| 一区二区久久| 欧美日韩mv| 亚洲大胆视频| 影音欧美亚洲| 久久精品国产综合| 久久精品国产免费| 国产视频亚洲精品| 午夜久久资源| 欧美在现视频| 国产农村妇女精品一二区| 一区二区三区四区国产| 一本综合精品| 欧美日韩免费在线| 日韩视频一区二区三区| 一区二区三区国产在线观看| 欧美激情亚洲激情| 亚洲欧洲在线观看| 99国产精品99久久久久久粉嫩| 欧美v国产在线一区二区三区| 免费一级欧美在线大片| 亚洲国产婷婷香蕉久久久久久99 | 亚洲一区二区在线播放| 亚洲一区二区视频| 国产精品久久久久久久久久ktv| 一区二区三区导航| 午夜宅男久久久| 国产一区二区激情| 久久久在线视频| 亚洲第一搞黄网站| 99国产精品视频免费观看一公开| 欧美精品色综合| 亚洲手机成人高清视频| 亚洲欧美制服另类日韩| 国产婷婷成人久久av免费高清| 久久成人人人人精品欧| 欧美成人r级一区二区三区| 亚洲精品中文字| 欧美午夜精品| 欧美在线视频免费观看| 亚洲大胆女人| 久久久久久久综合| 亚洲高清免费在线| 亚洲欧美日韩一区二区| 国内精品久久久久伊人av| 免费日韩成人| 亚洲一区二区视频在线| 欧美**人妖| 亚洲一级在线观看| 精品av久久久久电影| 欧美精品一区二区三区四区| 99视频在线精品国自产拍免费观看| 午夜精品偷拍| 最新热久久免费视频| 国产精品视频在线观看| 毛片av中文字幕一区二区| 亚洲一区二区三区在线| 欧美福利网址| 羞羞漫画18久久大片| 亚洲精品少妇| 国产一区二区三区在线观看免费 | 91久久在线| 国产一区99| 欧美日韩三级| 久久一区二区三区av| 亚洲无线视频| 亚洲国语精品自产拍在线观看| 久久精品亚洲一区二区| 亚洲天堂免费观看| 亚洲国产精品电影| 国内精品久久久久久久影视麻豆 | 久久久久免费视频| 亚洲午夜久久久久久久久电影院| 欧美韩日一区| 久久久久久久波多野高潮日日| 亚洲香蕉网站| 亚洲精品网站在线播放gif| 国内精品福利| 国产麻豆9l精品三级站| 欧美午夜宅男影院| 欧美黄网免费在线观看| 久久综合伊人77777| 欧美在线视频免费观看| 午夜精品久久| 亚洲免费在线观看| 夜夜嗨av一区二区三区四季av| 亚洲国产综合在线| 欧美福利视频在线| 欧美黄色日本| 欧美福利专区| 欧美国产日韩二区| 欧美成在线视频| 欧美mv日韩mv国产网站app| 久久久免费精品视频| 久久精品夜色噜噜亚洲aⅴ| 欧美在线免费观看亚洲| 午夜精品久久一牛影视| 欧美一级久久| 久久成人免费| 久久一区二区视频| 久久综合激情| 欧美大成色www永久网站婷| 欧美 日韩 国产精品免费观看| 欧美成人小视频| 亚洲国产一区二区在线| 99亚洲一区二区| 亚洲一区二区不卡免费| 欧美一区二区高清| 久久精品国内一区二区三区| 久久视频国产精品免费视频在线| 久久午夜视频| 欧美激情视频在线播放| 欧美亚洲成人免费| 国产欧美激情| 亚洲国产精品久久久久婷婷884 | 亚洲精品在线二区| 亚洲视频在线一区| 欧美主播一区二区三区| 久久综合伊人77777麻豆| 欧美激情一区在线观看| 亚洲美女av在线播放| 亚洲自拍偷拍一区| 久久在精品线影院精品国产| 欧美高清视频| 国产精品免费福利| 亚洲国产综合在线| 亚洲视频一区| 可以免费看不卡的av网站| 亚洲人成在线观看一区二区| 亚洲尤物精选| 蜜乳av另类精品一区二区| 国产精品爱久久久久久久| 国内精品视频在线播放| 亚洲视频在线免费观看| 另类春色校园亚洲| 中文精品99久久国产香蕉| 久久久人成影片一区二区三区 | 久久黄色网页| 欧美日韩一区综合| 亚洲成人自拍视频| 午夜精品剧场| 亚洲精品在线电影| 久久国产精品第一页| 欧美亚日韩国产aⅴ精品中极品| 狠狠色噜噜狠狠色综合久| 亚洲一区二区视频| 欧美激情一区二区三区| 欧美一区二区三区免费大片| 欧美激情无毛| 亚洲国产裸拍裸体视频在线观看乱了中文 | 西西裸体人体做爰大胆久久久| 亚洲国产精品第一区二区| 久久xxxx精品视频| 国产精品你懂的在线欣赏| 99成人在线|