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

gzwzm06
  C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
  1 隨筆 :: 52 文章 :: 17 評論 :: 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) 評論(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>
            
欧美破处大片在线视频|
亚洲人成毛片在线播放女女|
99re66热这里只有精品3直播|
午夜精彩国产免费不卡不顿大片|
99亚洲一区二区|
在线视频你懂得一区二区三区|
一本一本大道香蕉久在线精品|
一区二区三区视频在线播放|
一区二区三区日韩欧美精品|
亚洲综合二区|
久久一区中文字幕|
91久久久精品|
亚洲午夜精品视频|
久久精品国产77777蜜臀|
久久综合伊人77777|
欧美精品三区|
国产精品热久久久久夜色精品三区|
国产夜色精品一区二区av|
亚洲国产91精品在线观看|
亚洲精品一区二|
午夜精品久久久久影视
|
欧美成人精品三级在线观看
|
伊人色综合久久天天五月婷|
亚洲乱码视频|
欧美在线视频一区二区三区|
另类专区欧美制服同性|
99精品国产一区二区青青牛奶|
亚洲欧美日韩精品久久久久|
免费不卡在线观看|
国产乱码精品一区二区三区不卡
|
免费成人高清视频|
国产精品免费在线|
亚洲精品一区二区三区av|
欧美一区2区视频在线观看
|
久久久久久久综合色一本|
最新亚洲视频|
久久一二三四|
国产日韩精品在线观看|
亚洲美女av在线播放|
久久久精品国产一区二区三区|
亚洲日本一区二区|
久久男人资源视频|
国产中文一区|
欧美伊人久久大香线蕉综合69|
亚洲精品国产精品久久清纯直播|
欧美一区午夜精品|
国产精品综合视频|
亚洲欧美激情视频在线观看一区二区三区
|
亚洲尤物在线|
欧美大尺度在线|
国内精品久久久久久久影视蜜臀|
亚洲综合色婷婷|
亚洲精品女av网站|
久久精品视频播放|
国产亚洲欧美一区在线观看|
午夜精品久久久久久久|
亚洲少妇诱惑|
欧美日韩综合在线免费观看|
一本大道久久精品懂色aⅴ|
亚洲欧洲精品一区二区三区波多野1战4
|
亚洲天堂成人|
99视频一区二区|
欧美丝袜第一区|
亚洲欧美综合v|
亚洲欧美激情诱惑|
国产日韩欧美精品一区|
欧美一区观看|
欧美在线短视频|
亚洲高清av|
亚洲国产精品专区久久|
欧美激情在线|
亚洲欧美国产另类|
欧美在线亚洲一区|
在线成人亚洲|
亚洲啪啪91|
国产精品爱久久久久久久|
午夜精品理论片|
久久精品亚洲|
99视频一区二区|
亚洲欧美日韩精品久久亚洲区|
狠狠干综合网|
91久久精品一区二区别|
国产精品视频一区二区三区|
久久精品在线观看|
欧美黄色片免费观看|
亚洲欧美国产三级|
久久午夜色播影院免费高清|
日韩西西人体444www|
亚洲一区二区精品|
在线日韩欧美视频|
一本色道久久加勒比88综合|
国产亚洲综合性久久久影院|
亚洲啪啪91|
狠狠色噜噜狠狠狠狠色吗综合|
亚洲国产精品一区二区www在线|
国产精品久久久久久久免费软件|
久久夜色精品国产亚洲aⅴ|
欧美日韩高清不卡|
老司机免费视频一区二区三区|
欧美日韩免费一区二区三区|
久久精品水蜜桃av综合天堂|
欧美极品在线播放|
久久精品青青大伊人av|
欧美日韩国产一区精品一区|
久久综合给合|
国产精品亚洲不卡a|
亚洲国产精品毛片|
国产一区二区三区四区三区四|
亚洲国产精品一区二区久|
久久久久久久久岛国免费|
日韩亚洲欧美中文三级|
香蕉尹人综合在线观看|
99在线|亚洲一区二区|
久久精彩视频|
亚洲欧美综合v|
欧美日韩亚洲高清|
亚洲国产精品久久|
亚洲国产裸拍裸体视频在线观看乱了中文
|
欧美在线一二三|
欧美激情四色|
欧美激情成人在线|
韩国三级电影一区二区|
亚洲一级网站|
亚洲一区二区免费在线|
欧美大胆人体视频|
欧美不卡一卡二卡免费版|
国产亚洲一区二区三区在线观看|
亚洲午夜免费福利视频|
国产精品99久久久久久久久|
欧美国产视频在线观看|
欧美风情在线观看|
在线国产精品播放|
久久婷婷激情|
欧美成人中文字幕在线|
在线观看日韩一区|
猛干欧美女孩|
亚洲风情亚aⅴ在线发布|
亚洲高清在线视频|
欧美电影电视剧在线观看|
亚洲国产高潮在线观看|
亚洲免费成人av电影|
欧美区高清在线|
亚洲视频在线一区观看|
亚洲欧美伊人|
国产视频自拍一区|
久久九九精品99国产精品|
免费观看成人www动漫视频|
亚洲国产精品传媒在线观看
|
亚洲精品视频免费观看|
一区二区日韩伦理片|
国产精品草草|
欧美亚洲视频|
免费在线播放第一区高清av|
91久久国产精品91久久性色|
欧美大片在线观看一区|
99精品久久久|
久久精品一区中文字幕|
亚洲国产aⅴ天堂久久|
欧美日韩成人综合天天影院|
亚洲欧美日韩天堂一区二区|
久久久综合网站|
亚洲靠逼com|
国产伦精品一区二区三区免费迷|
久久国产精品网站|
亚洲美女在线观看|
久久久综合精品|
99pao成人国产永久免费视频|
国产精品区二区三区日本
|
国内综合精品午夜久久资源|
美乳少妇欧美精品|
亚洲无限av看|
亚洲国产成人精品久久|
久久精品女人天堂|
亚洲深夜福利|
免费在线看成人av|
9久re热视频在线精品|
久久精品在线播放|
在线综合亚洲欧美在线视频|
国产一区 二区 三区一级|
欧美大片91|
久久久久久久综合日本|
中文亚洲欧美|
欧美激情精品久久久久久免费印度|
亚洲综合精品四区|
91久久午夜|
在线观看三级视频欧美|
国产乱码精品|
国产精品wwwwww|
欧美精品日日鲁夜夜添|
久久久久久电影|
久久成人精品电影|
亚洲深夜av|
亚洲精一区二区三区|
欧美国产日韩一区|
久久免费精品视频|
久久精品国产亚洲a|
亚洲欧美999|
亚洲综合精品四区|
亚洲一级黄色|
亚洲永久精品国产|