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

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( 00, 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( 00, 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| 亚洲综合精品四区| 亚洲一级黄色| 亚洲永久精品国产|