希望有大佬看看哪里有问题
有的对有的不对
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2 * 300200;
const int INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx = 1;
int n,m;
int dep[N], fa[N], sz[N], son[N], tmp[N];
int id[N], nw[N],top[N], cnt;
struct node
{
int l,r;
int maxx, minn;
int sum;
int change;
}tr[N * 8];
struct p
{
int x,y;
}lr[N * 8];
void add(int a,int b,int c)
{
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++;
}
void dfs1(int u,int father,int depth)
{
dep[u] = depth;
fa[u] = father;
sz[u] = 1;
for(int i = h[u]; ~i; i = ne[i])
{
int y = e[i];
if(y == father)continue;
dfs1(y, u, depth + 1);
tmp[y] = w[i];
sz[u] += sz[y];
if(sz[son[u]] < sz[y])son[u] = y;
}
}
void dfs2(int u,int t)//top?
{
top[u] = t;
id[u] = ++ cnt;
nw[cnt] = tmp[u];
//nw[cnt] = w[u];
if(son[u])dfs2(son[u], t);
for(int i = h[u]; ~i; i = ne[i])
{
int y = e[i];
if(y == fa[u] || y == son[u])continue;
dfs2(y, y);
}
}
void pushup(int u)
{
tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
tr[u].minn = min(tr[u << 1].minn, tr[u << 1 | 1].minn);
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
if(tr[u].change)
{
tr[u << 1 | 1].change ^= 1;
tr[u << 1].change ^= 1;
tr[u << 1].sum = tr[u << 1].sum * (-1);
tr[u << 1 | 1].sum = tr[u << 1 | 1].sum * (-1);
tr[u << 1].maxx = -tr[u << 1].maxx;
tr[u << 1 | 1].maxx = -tr[u << 1 | 1].maxx;
tr[u << 1].minn = -tr[u << 1].minn;
tr[u << 1 | 1].minn = -tr[u << 1 | 1].minn;
swap(tr[u << 1].minn,tr[u << 1].maxx);
swap(tr[u << 1 | 1].minn,tr[u << 1 | 1].maxx );
tr[u].change = 0;
}
}
void build(int u,int l,int r)
{
tr[u].l = l, tr[u].r = r;
if(l == r)
{
tr[u].sum = nw[l];
tr[u].maxx = nw[l];
tr[u].minn = nw[l];
tr[u].change = 0;
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify_single(int u,int pos, int k)
{
if(tr[u].l == tr[u].r && tr[u].l == pos)
{
tr[u].sum = k;
tr[u].maxx = k;
tr[u].minn = k;
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(pos <= mid)modify_single(u << 1,pos,k);
if(pos > mid)modify_single(u << 1 | 1, pos, k);
pushup(u);
}
int query_maxx(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u].maxx;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int MAXX = -INF;
if(l <= mid)MAXX = max(MAXX, query_maxx(u << 1, l, r));
if(r > mid)MAXX = max(MAXX, query_maxx(u << 1 | 1, l, r));
pushup(u);
return MAXX;
}
int query_minn(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u].minn;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int MINN = INF;
if(l <= mid)MINN = min(MINN, query_minn(u << 1, l, r));
if(r > mid)MINN = min(MINN, query_minn(u << 1 | 1, l, r));
pushup(u);
return MINN;
}
void modify_range(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tr[u].sum = -tr[u].sum;
tr[u].maxx = -tr[u].maxx;
tr[u].minn = -tr[u].minn;
swap(tr[u].maxx, tr[u].minn);
tr[u].change ^= 1;
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid)modify_range(u << 1,l,r);
if(r > mid)modify_range(u << 1 | 1,l,r);
pushup(u);
}
int query_sum(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u].sum;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int ans = 0;
if(l <= mid)ans += query_sum(u << 1, l, r);
if(r > mid)ans += query_sum(u << 1 | 1, l,r );
pushup(u);
return ans;
}
void modify_r(int u,int v)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]])swap(u,v);
modify_range(1,id[top[u]],id[u]);
u = fa[top[u]];
}
if(dep[u] > dep[v])swap(u,v);
//if(u != v) moadify_range(1,id[v],id[u]);
if(u != v)modify_range(1, id[u] + 1, id[v]);
}
int query_ma(int u,int v)
{
int MAXX = -INF;
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]])swap(u,v);
MAXX = max(MAXX, query_maxx(1, id[top[u]], id[u]));
u = fa[top[u]];
}
if(dep[u] > dep[v])swap(u,v);
if(u != v)MAXX = max(MAXX, query_maxx(1, id[u] + 1, id[v]));
return MAXX;
}
int query_mi(int u,int v)
{
int MINN = INF;
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]])swap(u,v);
MINN = min(MINN, query_minn(1,id[top[u]], id[u]));
u = fa[top[u]];
}
if(dep[u] > dep[v])swap(u,v);
if(u != v)MINN = min(MINN, query_minn(1, id[u] + 1,id[v]));
return MINN;
}
int query_s(int u,int v)
{
int ans = 0;
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]])swap(u,v);
ans += query_sum(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if(dep[u] > dep[v])swap(u,v);
if(u != v)ans += query_sum(1, id[u] + 1, id[v]);
return ans;
}
signed main()
{
memset(h , -1, sizeof h);
scanf("%lld", &n);
for(int i = 1; i <= n - 1; i ++)
{
int a,b,c;
scanf("%lld%lld%lld", &a, &b, &c);
add(a + 1,b + 1,c);
add(b + 1,a + 1,c);
lr[i].x = a, lr[i].y = b;
}
//+ 1
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n);
scanf("%lld", &m);
while(m --)
{
char op[10];
int l,r,k;
scanf("%s", op);
if(op[0] == 'C')
{
int com;
scanf("%lld%lld", &l, &k);
if(dep[lr[l].x] > dep[lr[l].y])com = lr[l].x;
else com = lr[l].y;
//modify_s(1, id[l + 1], k);
modify_single(1, id[com], k);
}
else if(op[0] == 'N')
{
scanf("%lld%lld", &l, &r);
//modify_r(1, id[l + 1], id[r + 1]);
modify_r(l + 1, r + 1);
}
else if(op[0] == 'M' && op[1] == 'A')
{
scanf("%lld%lld", &l, &r);
//printf("%d\n", query_max(1,id[l + 1], id[r + 1]));
printf("%lld\n", query_ma(l + 1, r + 1));
}
else if(op[0] == 'S')
{
scanf("%lld%lld", &l, &r);
//printf("%d\n", query_sum(1,id[l + 1], id[r + 1]));
printf("%lld\n", query_s(l + 1, r + 1));
}
else if(op[0] == 'M' && op[1] == 'I')
{
scanf("%lld%lld", &l, &r);
//printf("%d\n", query_min(1,id[l + 1], id[r + 1]));
printf("%lld\n", query_mi(l + 1, r + 1));
}
}
return 0;
}