#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define MX 200005
#define LC sgs[now].lc
#define RC sgs[now].rc
struct Edge
{
int u, v, w;
};
Edge es[MX];
vector<int> to[MX];
struct Node
{
int fa, dp, hd, sz, zson, dfn, w;
};
Node ns[MX];
struct Seg
{
int lc, rc, vz, vf, tag, maxv, minv;
};
Seg sgs[MX * 4];
int ids[MX], npos, n, m, segroot, root = 1;
void dfs1(int now, int dp)
{
ns[now].dp = dp, ns[now].sz = 1;
for (int i : to[now])
{
int nxt = es[i].u + es[i].v - now, w = es[i].w;
if (nxt != ns[now].fa)
{
ns[nxt].fa = now, ns[nxt].w = w;
dfs1(nxt, dp + 1);
ns[now].sz += ns[nxt].sz;
if (ns[nxt].sz > ns[ns[now].zson].sz)
{
ns[now].zson = nxt;
}
}
}
}
void dfs2(int now, int hd)
{
ns[now].hd = hd, ns[now].dfn = ++npos;
ids[npos] = now;
if (ns[now].zson)
{
dfs2(ns[now].zson, hd);
}
for (int i : to[now])
{
int nxt = es[i].u + es[i].v - now;
if (nxt != ns[now].fa && nxt != ns[now].zson)
{
dfs2(nxt, nxt);
}
}
}
void update(int now)
{
sgs[now].maxv = max(sgs[LC].maxv, sgs[RC].maxv);
sgs[now].minv = min(sgs[LC].minv, sgs[RC].minv);
sgs[now].vz = sgs[LC].vz + sgs[RC].vz, sgs[now].vf = sgs[LC].vf + sgs[RC].vf;
}
void initsg(int &now, int l, int r)
{
now = ++npos;
if (l == r)
{
if (ns[ids[l]].w >= 0)
{
sgs[now].vz = ns[ids[l]].w;
}
else
{
sgs[now].vf = ns[ids[l]].w;
}
sgs[now].maxv = sgs[now].minv = ns[ids[l]].w;
return;
}
int mid = (l + r) / 2;
initsg(LC, l, mid), initsg(RC, mid + 1, r);
update(now);
}
void pushdown(int now)
{
if (sgs[now].tag)
{
sgs[LC].tag = !sgs[LC].tag, sgs[RC].tag = !sgs[RC].tag;
swap(sgs[LC].vz, sgs[LC].vf), swap(sgs[RC].vz, sgs[RC].vf);
sgs[LC].vz *= -1, sgs[LC].vf *= -1, sgs[RC].vz *= -1, sgs[RC].vf *= -1;
swap(sgs[LC].maxv, sgs[LC].minv), swap(sgs[RC].maxv, sgs[RC].minv);
sgs[LC].maxv *= -1, sgs[LC].minv *= -1, sgs[RC].maxv *= -1, sgs[RC].minv *= -1;
sgs[now].tag = 0;
}
}
void edit(int now, int l, int r, int x, int y, int k)
{
if (x <= l && y >= r)
{
if (k == 0x3f3f3f3f)
{
sgs[now].tag = !sgs[now].tag;
swap(sgs[now].vz, sgs[now].vf), swap(sgs[now].maxv, sgs[now].minv);
sgs[now].vz *= -1, sgs[now].vf *= -1, sgs[now].maxv *= -1, sgs[now].minv *= -1;
}
else
{
if (k >= 0)
{
sgs[now].vz = k, sgs[now].vf = 0;
}
else
{
sgs[now].vz = 0, sgs[now].vf = k;
}
sgs[now].maxv = sgs[now].minv = k;
}
return;
}
pushdown(now);
int mid = (l + r) / 2;
if (x <= mid)
{
edit(LC, l, mid, x, y, k);
}
if (y > mid)
{
edit(RC, mid + 1, r, x, y, k);
}
update(now);
}
int query(int now, int l, int r, int x, int y, int opt)
{
if (x <= l && y >= r)
{
if (opt == 1)
{
return sgs[now].vz + sgs[now].vf;
}
else if (opt == 2)
{
return sgs[now].maxv;
}
else
{
return sgs[now].minv;
}
}
pushdown(now);
int mid = (l + r) / 2, ans = 0;
if (opt == 1)
{
if (x <= mid)
{
ans += query(LC, l, mid, x, y, opt);
}
if (y > mid)
{
ans += query(RC, mid + 1, r, x, y, opt);
}
}
else if (opt == 2)
{
ans = -0x3f3f3f3f;
if (x <= mid)
{
ans = max(ans, query(LC, l, mid, x, y, opt));
}
if (y > mid)
{
ans = max(ans, query(RC, mid + 1, r, x, y, opt));
}
}
else
{
ans = 0x3f3f3f3f;
if (x <= mid)
{
ans = min(ans, query(LC, l, mid, x, y, opt));
}
if (y > mid)
{
ans = min(ans, query(RC, mid + 1, r, x, y, opt));
}
}
return ans;
}
int findAns(int a, int b, int opt)
{
int ans = 0;
if (opt == 2)
{
ans = -0x3f3f3f3f;
}
else if (opt == 3)
{
ans = 0x3f3f3f3f;
}
while (ns[a].hd != ns[b].hd)
{
if (ns[ns[a].hd].dp < ns[ns[b].hd].dp)
{
swap(a, b);
}
if (opt == 0)
{
edit(segroot, 1, n, ns[ns[a].hd].dfn, ns[a].dfn, 0x3f3f3f3f);
}
else if (opt == 1)
{
ans += query(segroot, 1, n, ns[ns[a].hd].dfn, ns[a].dfn, opt);
}
else if (opt == 2)
{
ans = max(ans, query(segroot, 1, n, ns[ns[a].hd].dfn, ns[a].dfn, opt));
}
else
{
ans = min(ans, query(segroot, 1, n, ns[ns[a].hd].dfn, ns[a].dfn, opt));
}
a = ns[ns[a].hd].fa;
}
if (a == b)
{
return ans;
}
if (ns[a].dp < ns[b].dp)
{
swap(a, b);
}
if (opt == 0)
{
edit(segroot, 1, n, ns[b].dfn + 1, ns[a].dfn, 0x3f3f3f3f);
}
else if (opt == 1)
{
ans += query(segroot, 1, n, ns[b].dfn + 1, ns[a].dfn, opt);
}
else if (opt == 2)
{
ans = max(ans, query(segroot, 1, n, ns[b].dfn + 1, ns[a].dfn, opt));
}
else
{
ans = min(ans, query(segroot, 1, n, ns[b].dfn + 1, ns[a].dfn, opt));
}
return ans;
}
int main()
{
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v, w;
cin >> u >> v >> w;
u++, v++;
to[u].push_back(i), to[v].push_back(i);
es[i].u = u, es[i].v = v, es[i].w = w;
}
dfs1(root, 1), dfs2(root, root);
npos = 0, initsg(segroot, 1, n);
cin >> m;
while (m--)
{
string opt;
int u, v;
cin >> opt >> u >> v;
if (opt == "C")
{
int a = es[u].u, b = es[u].v;
if (ns[b].fa == a)
{
swap(a, b);
}
edit(segroot, 1, n, ns[a].dfn, ns[a].dfn, v);
}
else if (opt == "N")
{
findAns(u + 1, v + 1, 0);
}
else if (opt == "SUM")
{
cout << findAns(u + 1, v + 1, 1) << endl;
}
else if (opt == "MAX")
{
cout << findAns(u + 1, v + 1, 2) << endl;
}
else
{
cout << findAns(u + 1, v + 1, 3) << endl;
}
}
return 0;
}
// TAG: 树链剖分 重链剖分 LCA 线段树 边权转点权 路径不包含LCA点权
OJCode-数据结构资源 （2000个子文件） 
P1505.cpp 7KB P2572.cpp 6KB P2590.cpp 4KB P3384.cpp 4KB P1126.cpp 4KB P3376 Hlpp.cpp 4KB P3178.cpp 4KB P7834.cpp 4KB P5494.cpp 4KB P4716.cpp 4KB P8820.cpp 4KB P4197.cpp 4KB P2414.cpp 3KB P3809.cpp 3KB P7456 Seg.cpp 3KB P7077.cpp 3KB P1098.cpp 3KB B3600.cpp 3KB P1081.cpp 3KB P2617.cpp 3KB P2787.cpp 3KB P5905.cpp 3KB P2596.cpp 3KB P2571.cpp 3KB P2023.cpp 3KB P1266.cpp 3KB P2216 DQ.cpp 3KB P3275.cpp 3KB P4556.cpp 3KB P1471.cpp 3KB P3629.cpp 3KB P5906.cpp 3KB P11234.cpp 3KB P8817.cpp 3KB P6136.cpp 3KB P3157.cpp 3KB P1262.cpp 3KB P1484.cpp 3KB P2464.cpp 3KB P2894.cpp 3KB T130013.cpp 3KB P1382.cpp 3KB P9979.cpp 3KB P3792.cpp 3KB P4001.cpp 3KB P1363.cpp 3KB P8818.cpp 3KB P11207.cpp 3KB P3761.cpp 3KB P7913.cpp 3KB P3402.cpp 3KB P7915.cpp 3KB P2046.cpp 3KB B3608.cpp 3KB P9122.cpp 3KB P1491.cpp 3KB P1538.cpp 3KB P4306.cpp 3KB P8890.cpp 3KB B3692.cpp 3KB P1209.cpp 3KB P1903.cpp 3KB P10059.cpp 3KB P3258.cpp 2KB P3586.cpp 2KB P8844.cpp 2KB P3124.cpp 2KB P1486.cpp 2KB P2704.cpp 2KB P2680.cpp 2KB P7910.cpp 2KB P1825.cpp 2KB P7261.cpp 2KB P3806.cpp 2KB P4097.cpp 2KB P3398.cpp 2KB P1058.cpp 2KB P3369 V2.cpp 2KB P2538.cpp 2KB P8463.cpp 2KB P7073.cpp 2KB P4281.cpp 2KB P7149.cpp 2KB P6186.cpp 2KB P4396.cpp 2KB P2357.cpp 2KB P3956.cpp 2KB P1247.cpp 2KB P1533.cpp 2KB P5522.cpp 2KB P8473.cpp 2KB P3372 Zkw.cpp 2KB P5195.cpp 2KB P7456.cpp 2KB P6378.cpp 2KB P2245 KruskalCG.cpp 2KB P5490.cpp 2KB P3627.cpp 2KB P5903.cpp 2KB P3007.cpp 2KB共 2000 条
- 1
- 2
- 3
- 4
- 5
- 6
- 20
资源评论
wjs2024
- 粉丝: 3431
最新资源
- 光伏并网逆变器闭环控制及MPPT技术解析：基于MatlabSimulinkPLECS的锁相环、LC滤波与MPPT控制
- 西门子S7-1200 PLC Modbus RTU 485通讯主站程序设计与实现 · Modbus RTU
- 基于COMSOL仿真平台的石蜡加热熔化多物理场耦合仿真：模拟温度和流场变化的案例分析
- Tiomehsh-datasheet-ai-analyzer-30136-1755665338791.zip
- 光伏储能微电网中Boost电路MPPT与双向Buck-Boost变换器对直流母线电压的精确调控 · SVPWM 详解
- 96三相多功能表：全套电路与源码详解，高精度实时电力参数测量与分析系统
- 电力系统中有源电力滤波器（APF）的仿真验证及其直流电压控制研究 · 电力系统
- 分别使用OpenCV、ONNXRuntime部署多任务的yolov5目标检测+语义分割，包含C++和Python两个版本的程序
- 三菱电梯主板参数详解：楼层显示、基站设置等关键功能调整 权威版
- 天鹰优化算法AO优化核极限学习机KELM参数的多输入单输出拟合预测建模的Matlab程序
- 网络空间安全导论2023学习项目-涵盖网络安全基础密码学原理恶意软件分析入侵检测技术数据保护策略安全协议设计风险评估方法应急响应流程法律法规遵循安全意识培养攻防.zip
- 基于IEEE33节点的风光储配电网优化调度仿真——经济成本最小化与潮流计算协同优化 · 分布式电源 手册
- 西门子PLC 12001500系列模拟量滤波技术解析：应对数据扰动的一阶惯性、蠕动平均值与中位值滤波
- 三相逆变器双闭环控制MATLAB Simulink模型设计：基于外环PR与内环比例控制策略的参数整定及建模原理参考
- 网络安全社区公开知识爬取工具-先知社区安全文章与漏洞分析报告自动化抓取与本地存储-实现高效知识管理与离线搜索功能-基于Selenium与BeautifulSoup4的自动化爬虫技术.zip
- YOLOv5 v6.2实例分割在LabVIEW工业应用中的高效推理与性能分析
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
