| 记录编号 |
230414 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[SPOJ 2666] QTREE4 |
最终得分 |
100 |
| 用户昵称 |
 dashgua |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.778 s |
| 提交时间 |
2016-02-21 19:24:23 |
内存使用 |
18.34 MiB |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
template<class Num>void read(Num &x)
{
int flag = 1;
char c;
while((c = getchar()) < '0' || c > '9')
if(c == '-') flag *= -1;
x = c - '0';
while((c = getchar()) >= '0' && c <= '9')
x *= 10, x += c - '0';
x *= flag;
}
template<class Num>void write(Num x)
{
if(x == 0) {putchar('0');return;}
if(x < 0) putchar('-'), x = -x;
static int stack[20];
int sl = 0;
while(x) stack[sl++] = x % 10, x /= 10;
while(sl) putchar(stack[--sl] + '0');
}
#define X first
#define Y second
#define L(x) ((x) << 1)
#define R(x) ((x) << 1 | 1)
const int maxn = 1e5 + 20, logN = 18, inf = 0x3f3f3f3f;
const int space = maxn << 2;
int *new_memory(int size)
{
static int array[space], *ind = array;
ind += size;
return ind - size;
}
std::pair<int,int> *new_memory_pair(int size)
{
static std::pair<int,int> array[space], *ind = array;
ind += size;
return ind - size;
}
struct Heap
{
int *pos, size, maxs;
std::pair<int,int> *heap;
void setup(int spsize)
{
maxs = spsize, pos = new_memory(maxs + 1);
heap = new_memory_pair(maxs + 1);
}
void update(int ind)
{
pos[heap[ind].Y] = ind;
}
void exchange(int a,int b)
{
std::swap(heap[a], heap[b]);
update(a), update(b);
}
void pushdown(int x)
{
int maxid = x;
if(L(x) <= size && heap[L(x)] > heap[maxid]) maxid = L(x);
if(R(x) <= size && heap[R(x)] > heap[maxid]) maxid = R(x);
if(maxid != x)
{
exchange(x, maxid);
pushdown(maxid);
}
}
void pushup(int x)
{
if(x == 1) return;
int fa = x >> 1;
if(heap[x] > heap[fa])
{
exchange(x, fa);
pushup(fa);
}
}
int top()
{
return size ? heap[1].X : -inf;
}
int tops()
{
if(size > 1)
{
if(size >= 3 && heap[3] > heap[2]) return heap[3].X;
return heap[2].X;
}
return -inf;
}
void pop()
{
if(size == 0) return;
pos[heap[1].Y] = 0;
std::swap(heap[1], heap[size--]);
if(size)
{
update(1);
pushdown(1);
}
}
void push(std::pair<int,int> t)
{
heap[++size] = t;
update(size);
pushup(size);
}
void change(int x,int y)
{
int t = pos[x];
heap[t].X = y;
pushdown(t);
pushup(t);
}
};
typedef std::pair<std::pair<int,int>,int> Seg;
int N, Q, white;
struct Edge
{
int v, w, next;
}edge[maxn << 1];
int head[maxn], el;
int top[maxn], son[maxn], size[maxn], dep[maxn], fa[maxn], dist[maxn];
int dfn[maxn], ind[maxn], dl, top_dep[maxn];
int top_ind[maxn], top_cnt[maxn], fw[maxn];
Heap node[maxn], ans;
Seg seg[maxn << 2];
bool flag[maxn];
void newedge(int u,int v,int w)
{
edge[++el] = (Edge){v, w, head[u]}, head[u] = el;
}
void init()
{
int a, b, c;
read(N);
for(int i = 1; i < N; i++)
{
read(a), read(b), read(c);
newedge(a, b, c);
newedge(b, a, c);
}
read(Q);
for(int i = 1; i <= N; i++) flag[i] = true;
white = N;
}
void dfs(int a)
{
size[a] = 1, dep[a] = dep[fa[a]] + 1;
for(int i = head[a]; i ; i = edge[i].next)
{
int p = edge[i].v;
if(p != fa[a])
{
dist[p] = dist[a] + edge[i].w;
fa[p] = a, fw[p] = edge[i].w, dfs(p);
if(size[p] > size[son[a]]) son[a] = p;
size[a] += size[p];
}
}
}
void build(int a)
{
dfn[++dl] = a, ind[a] = dl;
if(son[fa[a]] == a)
{
top[a] = top[fa[a]];
top_dep[top[a]] = a;
}
else
{
top[a] = a, top_dep[a] = a;
top_ind[a] = ++top_cnt[fa[a]];
}
if(son[a]) build(son[a]);
for(int i = head[a]; i ; i = edge[i].next)
{
int p = edge[i].v;
if(p != fa[a] && p != son[a]) build(p);
}
}
void update(int p,int l,int r)
{
int mid = (l + r) >> 1;
seg[p].X.X = std::max(seg[p << 1].X.X, seg[p << 1 | 1].X.X + dist[dfn[mid + 1]] - dist[dfn[l]]);
seg[p].X.Y = std::max(seg[p << 1 | 1].X.Y, seg[p << 1].X.Y + dist[dfn[r]] - dist[dfn[mid]]);
seg[p].Y = std::max(seg[p << 1].Y, seg[p << 1 | 1].Y);
seg[p].Y = std::max(seg[p << 1].X.Y + seg[p << 1 | 1].X.X + dist[dfn[mid + 1]] - dist[dfn[mid]], seg[p].Y);
}
Seg gather(Seg a,Seg b,int l,int d,int r)
{
Seg ret;
ret.X.X = std::max(a.X.X, b.X.X + dist[dfn[d + 1]] - dist[dfn[l]]);
ret.X.Y = std::max(b.X.Y, a.X.Y + dist[dfn[r]] - dist[dfn[d]]);
ret.Y = std::max(a.X.Y + b.X.X + dist[dfn[d + 1]] - dist[dfn[d]], std::max(a.Y, b.Y));
return ret;
}
void seg_build(int l,int r,int ll,int rr,int p)
{
if(ll == rr)
{
int maxL = std::max(node[dfn[l]].top(), flag[dfn[l]] ? 0 : -inf);
int maxR = std::max(node[dfn[l]].top(), flag[dfn[r]] ? 0 : -inf);
int opt = std::max(flag[dfn[l]] ? std::max(0, node[dfn[l]].top()) : -inf, node[dfn[l]].top() + node[dfn[l]].tops());
seg[p] = std::make_pair(std::make_pair(maxL, maxR), opt);
}
else
{
int mid = (ll + rr) >> 1;
if(r <= mid) seg_build(l, r, ll, mid, p << 1);
else if(l > mid) seg_build(l, r, mid + 1, rr, p << 1 | 1);
else
{
seg_build(l, mid, ll, mid, p << 1);
seg_build(mid + 1, r, mid + 1, rr, p << 1 | 1);
}
update(p, ll, rr);
}
}
void seg_update(int k,int l,int r,int p)
{
if(l == r)
{
int maxL = std::max(node[dfn[l]].top(), flag[dfn[l]] ? 0 : -inf);
int maxR = std::max(node[dfn[l]].top(), flag[dfn[r]] ? 0 : -inf);
int opt = std::max(flag[dfn[l]] ? std::max(0, node[dfn[l]].top()) : -inf, node[dfn[l]].top() + node[dfn[l]].tops());
seg[p] = std::make_pair(std::make_pair(maxL, maxR), opt);
}
else
{
int mid = (l + r) >> 1;
if(k <= mid) seg_update(k, l, mid, p << 1);
else seg_update(k, mid + 1, r, p << 1 | 1);
update(p, l, r);
}
}
Seg seg_query(int l,int r,int ll,int rr,int p)
{
if(l == ll && r == rr) return seg[p];
else
{
int mid = (ll + rr) >> 1;
if(r <= mid) return seg_query(l, r, ll, mid, p << 1);
else if(l > mid) return seg_query(l, r, mid + 1, rr, p << 1 | 1);
else return gather(seg_query(l, mid, ll, mid, p << 1), seg_query(mid + 1, r, mid + 1, rr, p << 1 | 1), l, mid, r);
}
}
void prework()
{
ans.setup(N);
for(int i = 1; i <= N; i++)
if(top_cnt[i]) node[i].setup(top_cnt[i]);
for(int i = N, j = N, t; i >= 1; i = j)
{
while(j > 0 && top[dfn[j]] == top[dfn[i]]) j--;
seg_build(j + 1, i, 1, N, 1), t = dfn[j + 1];
Seg w = seg_query(j + 1, i, 1, N, 1);
if(fa[t]) node[fa[t]].push(std::make_pair(w.X.X + fw[t], top_ind[t]));
ans.push(std::make_pair(w.Y, top[t]));
}
}
void solve()
{
char ch[3]; int x;
static int acnt = 0;
scanf("%s", ch);
if(ch[0] == 'C')
{
read(x);
if(flag[x])
white--, flag[x] = false;
else
white++, flag[x] = true;
for(int t = x; t; t = fa[top[t]])
{
seg_update(ind[t], 1, N, 1);
Seg k = seg_query(ind[top[t]], ind[top_dep[top[t]]], 1, N, 1);
if(fa[top[t]]) node[fa[top[t]]].change(top_ind[top[t]], k.X.X + fw[top[t]]);
ans.change(top[t], k.Y);
}
/*
for(int i = 1; i <= ans.size; i++)
std::cerr << ans.heap[i].X << std::endl;
*/
}
else
{
if(!white) puts("They have disappeared.");
else write(std::max(ans.top(), 0)), puts("");
}
}
int main()
{
freopen("QTREE4.in","r",stdin);
freopen("QTREE4.out","w",stdout);
init();
dfs(1), build(1);
prework();
while(Q--) solve();
fclose(stdin);
fclose(stdout);
return 0;
}