題目鏈接：點擊查看

題目大意：給出一個由n個點和n條邊組成的圖，每條邊都有權值，題目保證圖是連通的，然后給出m個詢問，每次詢問分為兩種形式：

0 x y：將第x條邊的權值修改為y

1 x y：查詢x-y這條路徑上的權值和

題目分析：因為這個題目故意給的是n個點和n條邊，所以我們可以發現這一定是一個有環的圖，如果n個點和n-1條邊組成一棵樹的話會多出一條邊來，那么先讓他多出來不要管，至于怎么求這個多出來的邊，我們直接用并查集操作一下就行了，因為上面也提到了，多出來一條邊肯定會組成環，所以多出來的那條邊會發現早就已經加入到集合中去了，單獨拿出來就行

針對這兩個操作我們需要分析一下，如果沒有第一個操作的話，那就是一個簡單的樹上求前綴和的問題了，我們只需要特判一下多出來的那條邊即可，大體思路就是先用樹上倍增或樹鏈剖分跑一下lca，然后用樹上前綴和求一下u-lca(u,v)-v這條路徑上的權值和，但是我們該怎么特判多出來的那條邊呢？

假如讓我們求的是x到y這條路徑上的權值和，而多出來的那條邊的兩個頂點是u和v，權值為w，那么我們可以先跑一下下面三個值，求一下最小值就是答案了：（sum[i]代表根節點到i節點的前綴和）

sum[x]+sum[y]-2*sum[lca(x,y)]//不經過多出來的那條邊：x-lca(x,y)-y

(sum[x]+sum[v]-2*sum[lca(x,v)])+(sum[y]+sum[u]-2*sum[lca(y,u)])+w//經過多出來的那條邊：x-lca(x,v)-v-u-lca(u,y)-y

(sum[x]+sum[u]-2*sum[lca(x,u)])+(sum[y]+sum[v]-2*sum[lca(y,v)])+w//經過多出來的那條邊：x-lca(x,u)-u-v-lca(v,y)-y

但是！這個題目是需要修改的，在樹上看到修改無非就是往線段樹和樹狀數組上靠攏了，因為我對樹狀數組的理解不太夠，所以還是選擇比較好用的線段樹來維護吧，具體就是先用樹鏈剖分將整個樹剖一下，然后因為邊權比較難處理，就將邊權映射到點權上，昨天剛做了一個類似的題目，于是就很好處理了，記著特別處理一下最后到根節點那條鏈上的關系就好，再一一對應到線段樹上，就可以寫一個getnum函數用來以logn*logn的時間復雜度獲取任意一點到根節點的權值和了，也就是上面提到的前綴和，然后對于修改操作的話，如果是多出來的那條邊，我們直接修改就行，如果是樹上的邊，用線段樹logn修改一下就好了，這個題我感覺比較討厭的地方是關于兩端映射，有兩個地方需要用到映射，一個是樹剖打dfs序的時候需要將序號和節點映射一下，還有就是關于每一條邊和映射到的節點也需要對應好，注意好這些細節，寫代碼盡量多用函數包裝一下，這樣寫完后debug起來也比較輕松

廢話不多說了，最后就是記得所有與權值相關的地方都開一下longlong，因為1e5*1e5就爆掉int了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int n,m;struct Edge {int u,v,id;LL w;Edge(int U,int V,LL W,int ID){u=U;v=V;w=W;id=ID;}Edge(){} }edge[N];//存邊用vector<Edge>node[N];//鄰接表struct Node {int l,r;LL sum; }tree[N<<2];//線段樹用int rk[N];//邊權與點權的映射 rk[編號]=節點LL val[N];//邊權與點權的映射 val[節點]=權值int id[N],idd[N];//dfs序與節點的映射 id[節點]=dfs序 idd[dfs序]=節點void pushup(int k)//以下為簡單線段樹維護sum和 {tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;if(l==r){tree[k].sum=val[idd[l]];return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int pos,int val) {if(tree[k].l==tree[k].r){tree[k].sum=val;return;}int mid=tree[k].l+tree[k].r>>1;if(mid>=pos)update(k<<1,pos,val);elseupdate(k<<1|1,pos,val);pushup(k); }LL query(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].sum;return query(k<<1,l,r)+query(k<<1|1,l,r); }int son[N],num[N],deep[N],fa[N];//樹鏈剖分用void dfs1(int u,int f,int dep) {fa[u]=f;son[u]=-1;num[u]=1;deep[u]=dep;for(int i=0;i<node[u].size();i++){int v=node[u][i].v;int w=node[u][i].w;int id=node[u][i].id;if(v==f)continue;val[v]=w;//將邊權映射到點權上 rk[id]=v;dfs1(v,u,dep+1);num[u]+=num[v];if(son[u]==-1||num[son[u]]<num[v])son[u]=v;} }int top[N],tot;//樹鏈剖分用void dfs2(int u,int f,int root) {top[u]=root;id[u]=++tot;idd[tot]=u;if(son[u]!=-1)dfs2(son[u],u,root);for(int i=0;i<node[u].size();i++){int v=node[u][i].v;if(v==f||v==son[u])continue;dfs2(v,u,v);} }LL getnum(int x)//獲得點1-點x的權值和 {LL ans=0;while(top[x]!=1){ans+=query(1,id[top[x]],id[x]);x=fa[top[x]];}if(x==1)return ans;ans+=query(1,2,id[x]);//注意這里，雖然這給題目從1開始和從2開始沒什么區別return ans; }int LCA(int a,int b)//樹鏈剖分求lca {while(top[a]!=top[b]){if(deep[top[a]]<deep[top[b]])swap(a,b);a=fa[top[a]];}if(a==b)return a;return deep[a]<deep[b]?a:b; }int f[N];//并查集用 int find(int x)//并查集 {return x==f[x]?x:f[x]=find(f[x]); }void init()//初始化 {for(int i=1;i<=n;i++){f[i]=i;node[i].clear();}tot=0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--)//按照上文中一步步實現即可{scanf("%d%d",&n,&m);init();int mark;for(int i=1;i<=n;i++){int u,v;LL w;scanf("%d%d%lld",&u,&v,&w);edge[i].u=u;edge[i].v=v;edge[i].w=w;edge[i].id=i;int uu=find(u);int vv=find(v);if(uu!=vv){f[uu]=vv;node[u].push_back(Edge(u,v,w,i));node[v].push_back(Edge(v,u,w,i));}elsemark=i;}dfs1(1,0,0);dfs2(1,0,1);build(1,1,n);while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(op==0){if(x==mark)edge[mark].w=y;elseupdate(1,id[rk[x]],y);}else{int lca=LCA(x,y);LL ans=getnum(x)+getnum(y)-2*getnum(lca);int u=edge[mark].u;int v=edge[mark].v;int w=edge[mark].w;LL ans1=getnum(x)+getnum(u)-2*getnum(LCA(x,u))+getnum(y)+getnum(v)-2*getnum(LCA(y,v));LL ans2=getnum(x)+getnum(v)-2*getnum(LCA(x,v))+getnum(y)+getnum(u)-2*getnum(LCA(y,u));printf("%lld\n",min(ans,min(ans1+w,ans2+w)));}}}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 6393 Traffic Network in Numazu(线段树+LCA+树链剖分+并查集)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。