| 记录编号 |
328102 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[国家集训队2011]旅游 |
最终得分 |
100 |
| 用户昵称 |
 sxysxy |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.283 s |
| 提交时间 |
2016-10-23 18:53:48 |
内存使用 |
11.37 MiB |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <string>
#include <list>
#include <queue>
#include <cctype>
using namespace std;
int fast_read()
{
int r;
char c;
bool sig = false;
while(c = getchar())
{
if(c == '-')sig = true;
else if(c >= '0' && c <= '9')
{
r = c^0x30;
break;
}
}
while(isdigit(c = getchar()))
r = (r<<3)+(r<<1)+(c^0x30);
return sig? -r:r;
}
#define MAXN 100003
struct edge
{
int from, to;
int value;
}edges[MAXN];
vector<int> G[MAXN];
int top[MAXN], size[MAXN], son[MAXN], deep[MAXN], parent[MAXN];
void dfs(int u, int f, int d)
{
size[u] = 1;
son[u] = -1;
deep[u] = d;
parent[u] = f;
for(int i = 0; i < G[u].size(); i++)
{
int to = G[u][i];
if(to != f)
{
dfs(to, u, d+1);
size[u] += size[to];
if(son[u] == -1)son[u] = to;
else if(size[to] > size[son[u]])
son[u] = to;
}
}
}
int has[MAXN];
int hasid = 0;
void dfs(int u, int tp)
{
has[u] = ++hasid;
top[u] = tp;
if(son[u] == -1)return;
dfs(son[u], tp);
for(int i = 0; i < G[u].size(); i++)
{
int to = G[u][i];
if(to != son[u] && to != parent[u])
dfs(to, to);
}
}
struct node
{
int l, r;
int ls, rs;
int sum;
int minv, maxv;
int lazy;
void flip()
{
minv = -minv;
maxv = -maxv;
swap(minv, maxv);
sum = -sum;
}
}ns[MAXN<<1];
int root = 1;
int last = root;
int val[MAXN];
#define ld ns[d.ls]
#define rd ns[d.rs]
void pushup(node &d)
{
d.sum = ld.sum + rd.sum;
d.maxv = max(ld.maxv, rd.maxv);
d.minv = min(ld.minv, rd.minv);
}
int build(int l, int r)
{
if(l > r)return 0;
int cur = last++;
node &d = ns[cur];
d.l = l;
d.r = r;
if(l == r)
d.sum = d.maxv = d.minv = val[l];
else
{
int m = (l+r)>>1;
d.ls = build(l, m);
d.rs = build(m+1, r);
pushup(d);
}
return cur;
}
void pushdown(node &d)
{
if(d.lazy)
{
ld.lazy ^= 1;
rd.lazy ^= 1;
ld.flip();
rd.flip();
d.lazy = 0;
}
}
int segtree_sum(int c, int l, int r)
{
if(!c)return 0;
node &d = ns[c];
if(l == d.l && r == d.r)
return d.sum;
else
{
pushdown(d);
if(l >= rd.l)return segtree_sum(d.rs, l, r);
else if(r <= ld.r)return segtree_sum(d.ls, l, r);
else return segtree_sum(d.ls, l, ld.r) + segtree_sum(d.rs, rd.l, r);
}
}
//复制粘贴大法好
int segtree_max(int c, int l, int r)
{
if(!c)return -0x7ffffffe;
node &d = ns[c];
if(l == d.l && r == d.r)
return d.maxv;
else
{
pushdown(d);
if(l >= rd.l)return segtree_max(d.rs, l, r);
else if(r <= ld.r)return segtree_max(d.ls, l, r);
else return max(segtree_max(d.ls, l, ld.r), segtree_max(d.rs, rd.l, r));
}
}
int segtree_min(int c, int l, int r)
{
if(!c)return 0x7fffffff;
node &d = ns[c];
if(l == d.l && r == d.r)
return d.minv;
else
{
pushdown(d);
if(l >= rd.l)return segtree_min(d.rs, l, r);
else if(r <= ld.r)return segtree_min(d.ls, l, r);
else return min(segtree_min(d.ls, l, ld.r), segtree_min(d.rs, rd.l, r));
}
}
void segtree_modify(int c, int pos, int v)
{
if(!c)return;
node &d = ns[c];
if(d.l == pos && d.r == d.l)
d.minv = d.maxv = d.sum = v;
else
{
pushdown(d);
if(pos >= rd.l)segtree_modify(d.rs, pos, v);
else if(pos <= ld.r)segtree_modify(d.ls, pos, v);
pushup(d);
}
}
void segtree_negate(int c, int l, int r)
{
if(!c)return;
node &d = ns[c];
if(d.l == l && d.r == r)
{
d.flip();
d.lazy ^= 1;
}else
{
pushdown(d);
if(l >= rd.l)segtree_negate(d.rs, l, r);
else if(r <= ld.r)segtree_negate(d.ls, l, r);
else
{
segtree_negate(d.ls, l, ld.r);
segtree_negate(d.rs, rd.l, r);
}
pushup(d);
}
}
int query_sum(int u, int v)
{
int t1 = top[u], t2 = top[v];
int ans = 0;
while(t1 != t2)
{
if(deep[t1] < deep[t2])
{
swap(u, v);
swap(t1, t2);
}
ans += segtree_sum(1, has[t1], has[u]);
u = parent[t1];
t1 = top[u];
}
if(u == v)return ans;
else
{
if(deep[u] < deep[v])swap(u, v);
return ans + segtree_sum(1, has[son[v]], has[u]);
}
}
int query_max(int u, int v)
{
//复制粘贴大法好
int t1 = top[u], t2 = top[v];
int ans = -0x7ffffffe;
while(t1 != t2)
{
if(deep[t1] < deep[t2])
{
swap(u, v);
swap(t1, t2);
}
ans = max(ans, segtree_max(1, has[t1], has[u]));
u = parent[t1];
t1 = top[u];
}
if(u == v)return ans;
else
{
if(deep[u] < deep[v])swap(u, v);
return max(ans, segtree_max(1, has[son[v]], has[u]));
}
}
int query_min(int u, int v)
{
//复制粘贴大法好
int t1 = top[u], t2 = top[v];
int ans = 0x7ffffffe;
while(t1 != t2)
{
if(deep[t1] < deep[t2])
{
swap(u, v);
swap(t1, t2);
}
ans = min(ans, segtree_min(1, has[t1], has[u]));
u = parent[t1];
t1 = top[u];
}
if(u == v)return ans;
else
{
if(deep[u] < deep[v])swap(u, v);
return min(ans, segtree_min(1, has[son[v]], has[u]));
}
}
void set_negate(int u, int v)
{
//复制粘贴大法好
int t1 = top[u], t2 = top[v];
while(t1 != t2)
{
if(deep[t1] < deep[t2])
{
swap(u, v);
swap(t1, t2);
}
segtree_negate(1, has[t1], has[u]);
u = parent[t1];
t1 = top[u];
}
if(u == v)return;
else
{
if(deep[u] < deep[v])swap(u, v);
segtree_negate(1, has[son[v]], has[u]);
}
}
void clear(int t)
{
while(t--)getchar();
}
int main()
{
freopen("nt2011_travel.in", "r", stdin);
freopen("nt2011_travel.out", "w", stdout);
int n = fast_read();
for(int i = 1; i < n; i++)
{
edge &e = edges[i];
e.from = fast_read();
e.to = fast_read();
e.value = fast_read();
G[e.from].push_back(e.to);
G[e.to].push_back(e.from);
}
dfs(0, -1, 1);
dfs(0, 0);
for(int i = 1; i < n; i++)
{
edge &e = edges[i];
if(deep[e.from] > deep[e.to])
swap(e.from, e.to);
val[has[e.to]] = e.value;
}
build(1, hasid);
int q = fast_read();
while(q--)
{
char c;
int u, v;
while(!isalpha(c = getchar()));
if(c == 'S')
{
clear(2);
u = fast_read();
v = fast_read();
printf("%d\n", query_sum(u, v));
}else if(c == 'N')
{
u = fast_read();
v = fast_read();
set_negate(u, v);
}else if(c == 'M')
{
char cc = getchar();
getchar();
if(cc == 'A')
{
u = fast_read();
v = fast_read();
printf("%d\n", query_max(u, v));
}else
{
u = fast_read();
v = fast_read();
printf("%d\n", query_min(u, v));
}
}else if(c == 'C')
{
u = fast_read();
v = fast_read();
segtree_modify(1, has[edges[u].to], v);
}
}
return 0;
}