P2680 運輸計劃
給定一棵樹和若幹條确定的路徑， 你可以将樹上一條邊權值變為 \(0\) ， 求變完以後給定路徑的最長長度最短
調試日志：
1. 樹剖部分， 對應到點的編号用了對應到線段樹上的編号
2. 二分寫反了（雖然很快就看到了）
簡記： 對應到樹上不管什麼都用 \(pos\) ， 對應到點上不管什麼都用 \(ori\)
Solution
艹, 考前心态炸裂， 連續狀态四天奇差， 頹了個星期天， 回來打代碼風生水起 \(1A\) 就是nima的爽
哦還有祝賀 \(IG\)
最大值最小， 聯想到二分答案
二分一個 \(k\)
具體的， 我們檢查給定路徑中長度大于 \(k\)， 若是這些路徑有 \(s\) 條
現在這 \(s\) 條路徑都不符合條件， 是以要是要将一條邊的邊權置為 \(0\)， 必須是這 \(s\) 條邊的交邊
不然就沒法将這 \(s\) 條邊總值一起變小了嘛
是以檢查思路為： 對于一個 \(k\)， 找出大于 \(k\) 的邊的交邊， 若最大邊 - 交邊 \(\leq k\) ， 則 \(k\) 合法
擷取給定路徑用樹剖加線段樹
注意邊權下放處理
檢查時因為是多次修改單次查詢， 可以用樹剖留下來的連續區間 + 差分 實作
差分數組字首和即為下放到ori[i]點的路徑的覆寫數
Code
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long
#define REP(i, x, y) for(int i = (x);i <= (y);i++)
using namespace std;
int RD(){
int out = 0,flag = 1;char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
return flag * out;
}
const int maxn = 600019,INF = 1e9 + 19;
int head[maxn],nume = 1;
struct Node{
int v,dis,nxt;
}E[maxn << 3];
void add(int u,int v,int dis){
E[++nume].nxt = head[u];
E[nume].v = v;
E[nume].dis = dis;
head[u] = nume;
}
int num, nr;
int dep[maxn], fa[maxn], size[maxn], val[maxn], top[maxn], wson[maxn];
int tot, pos[maxn], ori[maxn];
void dfs1(int u, int F){
size[u] = 1;
for(int i = head[u];i;i = E[i].nxt){
int v = E[i].v;
if(v == F)continue;
dep[v] = dep[u] + 1;
fa[v] = u;
val[v] = E[i].dis;//邊權下放
dfs1(v, u);
size[u] += size[v];
if(size[v] > size[wson[u]])wson[u] = v;
}
}
void dfs2(int u, int TP){
pos[u] = ++tot;
ori[tot] = u;
top[u] = TP;
if(!wson[u])return ;
dfs2(wson[u], TP);
for(int i = head[u];i;i = E[i].nxt){
int v = E[i].v;
if(v == fa[u] || v == wson[u])continue;
dfs2(v, v);
}
}
#define lid (id << 1)
#define rid (id << 1) | 1
struct seg_tree{
int l, r;
int sum;
}tree[maxn << 2];
void pushup(int id){tree[id].sum = tree[lid].sum + tree[rid].sum;}
void build(int id, int l, int r){
tree[id].l =l, tree[id].r = r;
if(l == r){
tree[id].sum = val[ori[l]];
return ;
}
int mid = (l + r) >> 1;
build(lid, l, mid), build(rid, mid + 1, r);
pushup(id);
}
int query(int id, int l, int r){
if(tree[id].l == l && tree[id].r == r)return tree[id].sum;
int mid = (tree[id].l + tree[id].r) >> 1;
if(mid < l)return query(rid, l, r);
else if(mid >= r)return query(lid, l, r);
return query(lid, l, mid) + query(rid, mid + 1, r);
}
int Q_sum(int x, int y){
int ret = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])swap(x, y);
ret += query(1, pos[top[x]], pos[x]);
x = fa[top[x]];
}
if(x == y)return ret;
if(dep[x] > dep[y])swap(x, y);
ret += query(1, pos[x] + 1, pos[y]);
return ret;
}
struct Edge{
int u, v, dis;
}I[maxn];
int D[maxn], maxx;//差分數組
void uprange(int x, int y){
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])swap(x, y);
D[pos[top[x]]] += 1;
D[pos[x] + 1] -= 1;
x = fa[top[x]];
}
if(x == y)return ;
if(dep[x] > dep[y])swap(x, y);
D[pos[x] + 1] += 1;
D[pos[y] + 1] -= 1;
}
bool check(int k){
int n = 0;
memset(D, 0, sizeof(D));
while(I[n + 1].dis > k){
n++;
uprange(I[n].u, I[n].v);
}
int sum = 0;
REP(i, 1, num){
sum += D[i];//差分數組字首和即為下放到ori[i]點的路徑的覆寫數
if(sum == n && maxx - val[ori[i]] <= k)return 1;
}
return 0;
}
int search(int l, int r){
int ans = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid))ans = mid, r = mid - 1;
else l = mid + 1;
}
return ans;
}
bool cmp(Edge a, Edge b){return a.dis > b.dis;}
int main(){
num = RD(), nr = RD();
REP(i, 1, num - 1){
int u = RD(), v = RD(), dis = RD();
add(u, v, dis), add(v, u, dis);
}
dep[1] = 1;
dfs1(1, -1);
dfs2(1, 1);
build(1, 1, num);
REP(i, 1, nr){
I[i].u = RD(), I[i].v = RD(), I[i].dis = Q_sum(I[i].u, I[i].v);
}
sort(I + 1, I + 1 + nr, cmp);
maxx = I[1].dis;//頭頭
printf("%d\n", search(0, maxx));
return 0;
} CG
轉載于:https://www.cnblogs.com/Tony-Double-Sky/p/9867384.html