Description

Input

Output

Sample Input

7 7 155
2 1 260
3 2 904
4 2 360
5 2 230
6 5 247
7 5 501
1 3
6 7
2 6
3 1
3 4
4 3
2 4

Sample Output

4104

Data Constraint

Solution

• 顯然，要改的邊一定是在某條路徑上最大值上，否則答案將得不到改變。

• 但又發現 最大值-L<次大值 的話，答案將不是那個最大值，而是那么次大值。

• 于是用倍增算出這 Q 條路徑上的 最大值、次大值的邊的編號。

• 接著按最大值的編號從小到大排一遍序，則相同編號的邊可以一起處理（表示一起刪除）。

• 那么把每種方案娶一個最小值即為答案，O((N+Q) log N) 。

Code

#include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+1; struct data {int x,y; }c[N],t; int tot=1; long long ans,all; int first[N],next[N<<1],en[N<<1],w[N<<1]; int f[N][17],g[N][17],h[N][17]; int a[N],b[N],dep[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void insert(int x,int y,int z) {next[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline void dfs(int x) {dep[x]=dep[f[x][0]]+1;for(int i=first[x];i;i=next[i])if(en[i]!=f[x][0]){f[en[i]][0]=x;g[en[i]][0]=i;dfs(en[i]);} } inline data lca(int x,int y) {if(dep[x]<dep[y]) swap(x,y);t.x=t.y=0;for(int i=log2(dep[x]);i>=0;i--)if(dep[f[x][i]]>=dep[y]){if(w[g[x][i]]>=w[t.x]){if(w[t.x]>w[h[x][i]]) t.y=t.x; else t.y=h[x][i];t.x=g[x][i];}elseif(w[g[x][i]]>w[t.y]) t.y=g[x][i];x=f[x][i];}if(x==y) return t;for(int i=log2(dep[x]);i>=0;i--)if(f[x][i]!=f[y][i]){if(w[g[x][i]]>=w[t.x]){if(w[t.x]>w[h[x][i]]) t.y=t.x; else t.y=h[x][i];t.x=g[x][i];}elseif(w[g[x][i]]>w[t.y]) t.y=g[x][i];if(w[g[y][i]]>=w[t.x]){if(w[t.x]>w[h[y][i]]) t.y=t.x; else t.y=h[y][i];t.x=g[y][i];}elseif(w[g[y][i]]>w[t.y]) t.y=g[y][i];x=f[x][i],y=f[y][i];}if(w[g[x][0]]>=w[t.x]){if(w[t.x]>w[h[x][0]]) t.y=t.x; else t.y=h[x][0];t.x=g[x][0];}elseif(w[g[x][0]]>w[t.y]) t.y=g[x][0];if(w[g[y][0]]>=w[t.x]){if(w[t.x]>w[h[y][0]]) t.y=t.x; else t.y=h[y][0];t.x=g[y][0];}elseif(w[g[y][0]]>w[t.y]) t.y=g[y][0];return t; } inline bool cmp(data x,data y) {return x.x>y.x; } int main() {int n=read(),q=read(),l=read();for(int i=1;i<n;i++){int x=read(),y=read(),z=read();insert(x,y,z);insert(y,x,z);}dfs(1);for(int j=1;j<17;j++)for(int i=1;i<=n;i++){f[i][j]=f[f[i][j-1]][j-1];if(w[g[i][j-1]]>w[g[f[i][j-1]][j-1]]){g[i][j]=g[i][j-1];if(w[h[i][j-1]]>w[g[f[i][j-1]][j-1]]) h[i][j]=h[i][j-1]; else h[i][j]=g[f[i][j-1]][j-1];}else{g[i][j]=g[f[i][j-1]][j-1];if(w[g[i][j-1]]>w[h[f[i][j-1]][j-1]]) h[i][j]=g[i][j-1]; else h[i][j]=h[f[i][j-1]][j-1];}}for(int i=1;i<=q;i++){a[i]=read(),b[i]=read();c[i]=lca(a[i],b[i]);all+=w[c[i].x];}sort(c+1,c+1+q,cmp);ans=all;for(int i=1;i<=q;i++){int k=i;long long sum=all;sum-=l;if(w[c[i].y]+l>w[c[i].x]) sum+=w[c[i].y]+l-w[c[i].x];while(k<q && c[k+1].x==c[i].x){k++;sum-=l;if(w[c[k].y]+l>w[c[k].x]) sum+=w[c[k].y]+l-w[c[k].x];}if(sum<ans) ans=sum;i=k;}printf("%lld",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5385. 【NOIP2017提高A组模拟9.23】Carry的全部內容，希望文章能夠幫你解決所遇到的問題。

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