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

gzwzm06
  C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
  1 隨筆 :: 52 文章 :: 17 評(píng)論 :: 0 Trackbacks
  1#include <cstdio>
  2
  3const int SIZE = 100001;
  4const int INF = 10000000;
  5
  6int N, arr_sc[SIZE], arr_order[SIZE], arr_index[SIZE], edge[SIZE][2], father[SIZE];
  7
  8struct NODE
  9{
 10    int m_v;
 11    struct NODE* next;
 12}tree[SIZE], mem[SIZE * 2];
 13
 14int index = 0, M = 0, tId = 1;
 15int gMax, gMin;
 16
 17struct ITEM
 18{
 19    int fst;
 20    int last;
 21}arr_pos[SIZE];
 22
 23struct STREE
 24{
 25    int m_start;
 26    int m_end;
 27
 28    int m_max;
 29    int m_min;
 30    int m_markMin;
 31    int m_markMax;
 32
 33    int m_leftChild;
 34    int m_rightChild;
 35}stree[SIZE * 2];
 36
 37void Insert(const int& x, const int& y)
 38{
 39    mem[index].m_v = y;
 40    mem[index].next = tree[x].next;
 41    tree[x].next = &mem[index];
 42    index++;
 43
 44    mem[index].m_v = x;
 45    mem[index].next = tree[y].next;
 46    tree[y].next = &mem[index];
 47    index++;
 48}
 49
 50void DFS( const int &root, const int& fat )
 51{
 52    NODE *ptr = tree[root].next;
 53    
 54    arr_pos[root].fst = M;
 55    arr_index[root] = M;
 56    arr_order[M++] = root;
 57    father[root] = fat;
 58
 59    while ( ptr )
 60    {
 61        if ( ptr->m_v != fat )
 62        {
 63            DFS( ptr->m_v, root );
 64        }
 65        ptr = ptr->next;
 66    }
 67
 68    arr_pos[root].last = M - 1;
 69}
 70
 71void Build(const int& id, const int& s, const int& e)
 72{
 73    stree[id].m_start = s;
 74    stree[id].m_end = e;
 75    stree[id].m_max = 0;
 76    stree[id].m_min = INF;
 77    stree[id].m_markMax = -1;
 78    stree[id].m_markMin = -1;
 79    if ( s == e )
 80    {
 81        return;
 82    }
 83
 84    int mid = (s + e) >> 1;
 85
 86    stree[id].m_leftChild = tId++;
 87    Build( stree[id].m_leftChild, s, mid );
 88
 89    stree[id].m_rightChild = tId++;
 90    Build( stree[id].m_rightChild, mid + 1, e );
 91}
 92
 93void InsertTree(const int& id, const int& p, const int& v)
 94{
 95    if ( stree[id].m_max < v )
 96    {
 97        stree[id].m_max = v;
 98        stree[id].m_markMax = arr_order[p];
 99    }
100    if ( stree[id].m_min > v )
101    {
102        stree[id].m_min = v;
103        stree[id].m_markMin = arr_order[p];
104    }
105
106    if ( stree[id].m_start == p && stree[id].m_end == p )
107    {
108        return;
109    }
110
111    int mid = (stree[id].m_start + stree[id].m_end) >> 1;
112
113    if ( mid >= p )
114        InsertTree( stree[id].m_leftChild, p, v );
115    else
116        InsertTree( stree[id].m_rightChild, p, v );
117}
118
119void Change( const int& id, const int& p, const int& v )
120{
121    if ( stree[id].m_markMax == arr_order[p] )
122    {
123        stree[id].m_max = 0;
124        stree[id].m_markMax = -1;
125    }
126    if ( stree[id].m_markMin == arr_order[p] )
127    {
128        stree[id].m_min = INF;
129        stree[id].m_markMin = -1;
130    }
131
132    if ( stree[id].m_leftChild == p && stree[id].m_rightChild == p )
133    {
134        stree[id].m_max = stree[id].m_min = v;
135        stree[id].m_markMax = stree[id].m_markMin = arr_order[p];
136        return;
137    }
138
139    int mid = (stree[id].m_start + stree[id].m_end) >> 1;
140
141    if ( mid >= p )
142    {
143        Change( stree[id].m_leftChild, p, v );
144    }
145    else {
146        Change( stree[id].m_rightChild, p, v );
147    }
148
149    int tf = stree[id].m_leftChild, tr = stree[id].m_rightChild, tmark, ts;
150    
151    ts = (stree[tf].m_max > stree[tr].m_max ? stree[tf].m_max : stree[tr].m_max);
152    tmark = (stree[tf].m_max > stree[tr].m_max ? stree[tf].m_markMax : stree[tr].m_markMax );
153    if ( stree[id].m_max < ts )
154    {
155        stree[id].m_max = ts;
156        stree[id].m_markMax = tmark;
157    }
158
159    ts = (stree[tf].m_min < stree[tr].m_min ? stree[tf].m_min : stree[tr].m_min);
160    tmark = (stree[tf].m_min < stree[tr].m_min ? stree[tf].m_markMin : stree[tr].m_markMin );
161    if ( stree[id].m_min > ts )
162    {
163        stree[id].m_min = ts;
164        stree[id].m_markMin = tmark;
165    }
166
167}
168
169void Query(const int& id, const int& s, const int& e)
170{
171    if ( s == stree[id].m_start && e == stree[id].m_end )
172    {
173        if ( gMax < stree[id].m_max )
174            gMax = stree[id].m_max;
175        if ( gMin > stree[id].m_min )
176            gMin = stree[id].m_min;
177
178        return;
179    }
180
181    int mid = (stree[id].m_start + stree[id].m_end) >> 1;
182
183    if ( mid >= e )
184    {
185        Query( stree[id].m_leftChild, s, e );
186    }
187    else if ( mid < s )
188    {
189        Query( stree[id].m_rightChild, s, e );
190    }
191    else {
192        Query( stree[id].m_leftChild, s, mid );
193        Query( stree[id].m_rightChild, mid + 1, e );
194    }
195}
196
197void Solve(const int& ep)
198{
199    gMax = 0;
200    gMin = INF;
201
202    __int64 ans;
203    int x, y, s, e;
204
205    x = edge[ep][0], y = edge[ep][1];
206
207    if ( y == father[x] )
208        y = x;
209
210    s = arr_pos[y].fst;
211    e = arr_pos[y].last;
212
213    if ( s == e )
214    {
215        gMax = gMin = arr_sc[y];
216    }
217    else {
218        Query( 0, s, e );
219    }
220
221    ans = gMax * gMin;
222
223    gMax = 0;
224    gMin = INF;
225
226    if ( s > 0 )
227        Query( 0, 0, s - 1 );
228
229    if ( e + 1 <= M - 1 )
230        Query( 0, e + 1, M - 1 );
231
232    ans += gMax * gMin;
233
234    printf("%I64d\n", ans);
235
236}
237
238void Init()
239{
240    int i;
241
242    for ( i = 0; i < SIZE; ++i )
243        tree[i].next = NULL;
244
245    index = 0;
246    tId = 1;
247    M = 0;
248}
249
250int main()
251 {
252     freopen("1.txt", "r", stdin);
253
254     int cs;
255     int i, x, y, Q;
256     char cmd[10];
257
258     scanf("%d", &cs);
259
260     while ( cs-- )
261     {
262         scanf("%d %d", &N, &Q);
263
264         for ( i = 1; i <= N; ++i )
265         {
266             scanf("%d", &arr_sc[i]);
267         }
268
269         Init();
270         Build( 0, 0, N - 1 );
271
272         for ( i = 0; i < N - 1; ++i )
273         {
274             scanf("%d %d", &x, &y);
275
276             edge[i + 1][0] = x;
277             edge[i + 1][1] = y;
278             Insert( x, y );
279         }
280
281         father[1] = -1;
282         DFS( 1, -1 );
283
284         for ( i = 0; i < M; ++i )
285         {
286             int t = arr_order[i];
287             InsertTree( 0, i, arr_sc[t] );
288         }
289
290         for ( i = 0; i < Q; ++i )
291         {
292             scanf("%s", cmd);
293
294             if ( cmd[0] == 'Q' )
295             {
296                 scanf("%d", &x);
297            
298                 Solve( x );
299             }
300             else if ( cmd[0] == 'C' )
301             {
302                 scanf("%d %d", &x, &y);
303                 arr_sc[x] = y;
304                 Change( 0, arr_index[x], y ); 
305             }
306         }
307     }
308     
309     return 0;
310 }
311
posted on 2009-05-20 00:13 巫 閱讀(317) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <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精品国产一区二区青青牛奶|
亚洲黄色av一区|
欧美大香线蕉线伊人久久国产精品|
亚洲高清av|
亚洲视频 欧洲视频|
国产九九视频一区二区三区|
欧美一区在线看|
欧美国产日本|
亚洲一区二区在线视频|
国产日韩在线不卡|
麻豆免费精品视频|
一本色道久久加勒比88综合|
久久都是精品|
亚洲激情第一区|
国产精品色婷婷|
噜噜噜噜噜久久久久久91
|
国产精品视频自拍|
久久都是精品|
日韩亚洲视频|
麻豆精品在线视频|
亚洲一区二区三区四区中文
|
欧美激情无毛|
午夜综合激情|
91久久久精品|
国产一区在线播放|
欧美日韩中文字幕综合视频|
久久av在线|
一本大道久久a久久精品综合|
久久精品一二三区|
在线一区二区三区四区|
精品电影在线观看|
国产精品捆绑调教|
欧美国产日产韩国视频|
久久精彩免费视频|
在线一区二区日韩|
亚洲欧洲日产国产综合网|
久久精品国产96久久久香蕉|
亚洲少妇中出一区|
亚洲日本视频|
在线观看国产精品淫|
国产精品免费在线|
欧美日韩色婷婷|
欧美aⅴ一区二区三区视频|
欧美一区二区三区久久精品茉莉花
|
欧美激情精品久久久久久免费印度
|
亚洲欧美一区二区激情|
亚洲日本欧美|
在线欧美影院|
黄色精品免费|
国产亚洲欧美中文|
国产精品自拍小视频|
欧美视频在线观看一区|
欧美国产日韩精品|
免费久久99精品国产自在现线|
久久成人亚洲|
久久精品一区二区三区不卡牛牛
|
欧美日韩国产区|
欧美成在线观看|
欧美寡妇偷汉性猛交|
久久午夜羞羞影院免费观看|
午夜综合激情|
篠田优中文在线播放第一区|
亚洲女人天堂成人av在线|
在线一区欧美|
亚洲在线播放|
亚洲欧美日韩在线|
性欧美1819性猛交|
午夜日韩在线|
久久精品99国产精品酒店日本|
欧美一区二区三区视频免费播放|
亚洲欧美激情诱惑|
亚洲综合色激情五月|
午夜老司机精品|
久久精品人人|
久久亚洲视频|
欧美激情91|
欧美日韩在线观看一区二区|
国产精品家教|
国产三级欧美三级|
影音先锋另类|
亚洲精品视频啊美女在线直播|
日韩一区二区免费高清|
一本色道久久综合亚洲精品小说|
亚洲视频高清|
久久电影一区|
欧美成人在线影院|
日韩视频免费在线|
亚洲午夜精品17c|
久久激情综合网|
欧美成人蜜桃|
国产精品任我爽爆在线播放|
国产区欧美区日韩区|
在线免费观看欧美|
一本色道久久综合亚洲精品按摩|
亚洲欧美另类中文字幕|
久久久无码精品亚洲日韩按摩|
美女久久网站|
亚洲精品日产精品乱码不卡|
亚洲一区中文|
麻豆av一区二区三区久久|
欧美三级不卡|
狠色狠色综合久久|
在线亚洲高清视频|
久久在线91|
99re66热这里只有精品4|
欧美亚洲免费电影|
欧美激情区在线播放|
国产日韩欧美一区二区三区在线观看|
精品999成人|
亚洲影院一区|
欧美韩日一区|
午夜精品视频在线观看一区二区|
免费成人你懂的|
国产精品永久入口久久久|
91久久精品国产91久久|
欧美在线观看视频一区二区|
亚洲第一伊人|
久久黄色影院|
国产精品久久一级|
亚洲七七久久综合桃花剧情介绍|
亚洲无限乱码一二三四麻|
亚洲一区制服诱惑|
久久综合给合|
一区二区电影免费观看|
久久www成人_看片免费不卡|
欧美日本亚洲视频|
国产一区二区三区在线观看网站
|
亚洲色图综合久久|
欧美aa在线视频|
亚洲视频在线一区观看|
蜜臀久久99精品久久久久久9|
欧美日韩一区在线|
国产亚洲欧美另类中文|
亚洲一区二区不卡免费|
媚黑女一区二区|
亚洲免费在线观看|
欧美激情综合在线|
伊人成年综合电影网|
亚洲在线电影|
欧美激情国产日韩|
欧美在线观看日本一区|
欧美三级电影一区|
亚洲视频日本|
亚洲高清不卡一区|
欧美自拍偷拍|
国产精品亚洲一区二区三区在线|
亚洲电影在线|
欧美成人精品不卡视频在线观看|
亚洲天堂成人在线视频|
欧美精品三级|
亚洲人人精品|
玖玖精品视频|
久久精品国产亚洲一区二区|
国产精品区二区三区日本|
日韩午夜激情|
最新亚洲电影|
欧美日韩一区高清|
99国产精品私拍|
欧美韩国日本一区|
久久这里只精品最新地址|
亚洲国产网站|
欧美va天堂|
久久综合激情|
激情综合网址|
美女免费视频一区|
樱花yy私人影院亚洲|
中文无字幕一区二区三区|
欧美国产在线观看|
久久久久久久999精品视频|
经典三级久久|
男人天堂欧美日韩|
久久久综合香蕉尹人综合网|
黑人中文字幕一区二区三区|
麻豆精品视频在线观看视频|
久久精品国产精品亚洲综合|
国产日韩欧美成人|
久久国产乱子精品免费女|
久久精品91久久久久久再现|
国产专区综合网|
久久蜜桃av一区精品变态类天堂|
欧美一区二区三区的|
国产欧美精品在线播放|
美女精品网站|
免费观看在线综合|
99综合在线|
一本久久a久久精品亚洲|
国产欧美日韩亚洲精品|
久久精品一二三区|
久久噜噜亚洲综合|
亚洲国产专区|
亚洲一区二区成人|
国模大胆一区二区三区|
蜜臀av一级做a爰片久久|
浪潮色综合久久天堂|
亚洲综合色视频|
午夜欧美电影在线观看|
亚洲国产精品久久久久秋霞不卡|
亚洲午夜精品一区二区|