|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 柿子饼同学 于 2023-9-28 10:37 编辑
题目: P4315
不要用 GPT 回复....
求助求助 , 样例过了但是 0 分 , 必有鱼币重谢
多谢了...
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1e5 + 5;
- int n, u, v, w, k;
- vector<int> e[N], d[N], id[N];
- // e 是树, d 是每条边的边权, id 是每条边的编号
- // 因为不会链式前向星...
- map<int, int> dict;
- // dict 返回一个编号的边对应的节点编号
- int data[N];
- // 每个边的值, 为了方便都会转移到这条边上深度较大的点上
- int size[N], hc[N], pa[N], dep[N];
- // hc 是重孩子
- int dfn[N], rdfn[N], top[N], tot;
- string op;
- void dfs1(int u, int par){
- size[u] = 1;
- pa[u] = par;
- dep[u] = dep[par] + 1;
- for(int i = 0; i < e[u].size(); i++){
- if(e[u][i] == par) continue;
- data[e[u][i]] = d[u][i];
- dict[id[u][i]] = e[u][i];
- dfs1(e[u][i], u);
- size[u] += size[e[u][i]];
- if(size[e[u][i]] > size[hc[u]]) hc[u] = e[u][i];
- }
- }
- void dfs2(int u, int t){
- top[u] = t;
- dfn[u] = ++tot;
- rdfn[tot] = u;
- if(!hc[u]) return ;
- dfs2(hc[u], t);
- for(auto ed : e[u]){
- if(ed == pa[u] || ed == hc[u]) continue;
- dfs2(ed, ed);
- }
- }
- struct Segment_Tree{
- #define lc u<<1
- #define rc u<<1|1
- struct Node{
- int l, r, tr, add, maxv;
- } t[N << 2];
- void pushup(int u){
- t[u].maxv = max(t[lc].maxv, t[rc].maxv);
- }
- void pushdown(int u){
- if(t[u].tr){
- t[lc].tr = t[rc].tr = t[u].tr;
- t[lc].maxv = t[rc].maxv = t[u].tr;
- t[lc].add = t[rc].add = 0;
- t[u].tr = 0;
-
- }
- if(t[u].add){
- t[lc].maxv += t[u].add;
- t[lc].add += t[u].add;
- t[rc].maxv += t[u].add;
- t[rc].add += t[u].add;
- t[u].add = 0;
- }
- }
- void build(int u, int l, int r){
- t[u] = {l, r};
- if(l == r){
- t[u].maxv = data[rdfn[l]];
- t[u].add = t[u].tr = 0;
- return ;
- }
- auto mid = (l + r) >> 1;
- build(lc, l, mid);
- build(rc, mid + 1, r);
- pushup(u);
- }
- void trans(int u, int l, int r, int val){ // 全部改
- if(l <= t[u].l && t[u].r <= r){
- t[u].tr = val;
- t[u].maxv = val;
- return ;
- }
- auto mid = (t[u].l + t[u].r) >> 1;
- pushdown(u);
- if(l <= mid) trans(lc, l, r, val);
- if(r > mid) trans(rc, l, r, val);
- pushup(u);
- }
- void modify(int u, int l, int r, int val){ // 区间加
- if(l <= t[u].l && t[u].r <= r){
- t[u].add += val;
- t[u].maxv += val;
- return ;
- }
- auto mid = (t[u].l + t[u].r) >> 1;
- pushdown(u);
- if(l <= mid) modify(lc, l, r, val);
- if(r > mid) modify(rc, l, r, val);
- pushup(u);
- }
- int query(int u, int l, int r){
- if(l <= t[u].l && t[u].r <= r){
- return t[u].maxv;
- }
- auto mid = (t[u].l + t[u].r) >> 1;
- int res = 0;
- pushdown(u);
- if(l <= mid) res = max(res, query(lc, l, r));
- if(r > mid) res = max(res, query(rc, l, r));
- return res;
- }
- } sgt;
- int Max(int u, int v){
- int res = 0;
- while(top[u] != top[v]){
- if(dep[top[u]] < dep[top[v]]) swap(u, v);
- res = max(res, sgt.query(1, dfn[top[u]], dfn[u]));
- u = pa[top[u]];
- }
- res = max(res, sgt.query(1, min(dfn[u], dfn[v]), max(dfn[u], dfn[v])));
- return res;
- }
- void Change(int k, int w){
- sgt.trans(1, dfn[k], dfn[k], w);
- }
- void Cover(int u, int v, int w){
- while(top[u] != top[v]){
- if(dep[top[u]] < dep[top[v]]) swap(u, v);
- sgt.trans(1, dfn[top[u]], dfn[u], w);
- u = pa[top[u]];
- }
- sgt.trans(1, min(dfn[u], dfn[v]), max(dfn[u], dfn[v]), w);
- }
- void Add(int u, int v, int w){
- while(top[u] != top[v]){
- if(dep[top[u]] < dep[top[v]]) swap(u, v);
- sgt.modify(1, dfn[top[u]], dfn[u], w);
- u = pa[top[u]];
- }
- sgt.modify(1, min(dfn[u], dfn[v]), max(dfn[u], dfn[v]), w);
- }
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> n;
- for(int i = 1; i < n; i++){
- cin >> u >> v >> w;
- e[u].emplace_back(v);
- e[v].emplace_back(u);
- d[u].emplace_back(w);
- d[v].emplace_back(w);
- id[u].emplace_back(i);
- id[v].emplace_back(i);
- }
- dfs1(1, 0);
- dfs2(1, 1);
- sgt.build(1, 1, n);
- while(cin >> op){
- if(op[0] == 'S') break;
- if(op[0] == 'C'){
- if(op[1] == 'h'){
- cin >> k >> w;
- Change(dict[k], w);
- }
- else{
- cin >> u >> v >> w;
- Cover(u, v, w);
- }
- }
- else if(op[0] == 'A'){
- cin >> u >> v >> w;
- Add(u, v, w);
- }
- else{
- cin >> u >> v;
- cout << Max(u, v) << '\n';
- }
- }
- return 0;
- }
复制代码
|
|