题目大意: 给你一棵 n 个节点的树, 这 n 条边称为原边, 另给出 m 条带权值的额外边, 求删去每条原边后通过给出的 m 额外条边变回一棵树的最小价值.
题解:
看完题面以为是 Tarjan 连通性之类的题目, 冷静分析后想到是树链剖分, 自己真是 Too young too simple.
首先将这棵树进行树链剖分, 对于每条额外边 x-y, 可以作为原树上 x-y 的路径上的任意一条边删去时的答案, 所以路径更新最小值即可.
树链剖分 + 线段树维护区间最小值, 边权转点权的技巧直接把这条边的权值赋到儿子节点上, 查找更新时不找 LCA 即可...
输出要求是按原边的顺序, 这里用了一个小技巧, 大家手模感性理解一下就好了.
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #include<string>
- #include<map>
- #include<iostream>
- #include<queue>
- using namespace std;
- #define isNum(a) (a>='0'&&a<='9')
- #define SP putchar(' ')
- #define EL putchar('\n')
- #define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
- template<class T1>void read(T1 &r_e_a_d);
- template<class T1>void write(T1 w_r_i_t_e);
- const int N=50005;
- int n,m,len=1,x,y,z,a[N],head[N],idn[N],idw[N];
- struct EDGE{
- int to,next,id;
- }edge[N<<1];
- void add(int x,int y,int d){
- ++len;
- edge[len].to=y;edge[len].next=head[x];edge[len].id=d;head[x]=len;
- }
- int dep[N],son[N],siz[N],fa[N];
- void dfs1(int u,int father){
- dep[u]=dep[father]+1;fa[u]=father;siz[u]=1;
- for (register int i=head[u];i;i=edge[i].next){
- int v=edge[i].to;
- if (v!=father){
- dfs1(v,u);siz[u]+=siz[v];
- if (son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
- idn[v]=edge[i].id;
- }
- }
- }
- int tot,top[N],dfn[N],seg[N];
- void dfs2(int u,int tp){
- top[u]=tp;
- dfn[u]=++tot;
- seg[dfn[u]]=u;
- if (son[u]==-1) return ;
- dfs2(son[u],tp);
- for (register int i=head[u];i;i=edge[i].next){
- int v=edge[i].to;
- if (v!=fa[u]&&v!=son[u]){
- dfs2(v,v);
- }
- }
- }
- int tree[50005<<2],lazy[50005<<2];
- void build(int k,int l,int r){
- tree[k]=lazy[k]=1<<30;
- if (l==r) return ;
- int mid=l+r>>1;
- build(k<<1,l,mid);build(k<<1|1,mid+1,r);
- }
- void pushdown(int k){
- tree[k<<1]=min(tree[k<<1],lazy[k]);
- tree[k<<1|1]=min(tree[k<<1|1],lazy[k]);
- lazy[k<<1]=min(lazy[k],lazy[k<<1]);
- lazy[k<<1|1]=min(lazy[k],lazy[k<<1|1]);
- lazy[k]=1<<30;
- }
- void modify(int k,int l,int r,int x,int y,int z){
- if (x<=l&&r<=y){
- tree[k]=min(tree[k],z);
- lazy[k]=min(lazy[k],z);
- return ;
- }
- if (lazy[k]!=1<<30) pushdown(k);
- int mid=l+r>>1;
- if (x<=mid) modify(k<<1,l,mid,x,y,z);
- if (mid<y) modify(k<<1|1,mid+1,r,x,y,z);
- tree[k]=min(tree[k<<1],tree[k<<1|1]);
- }
- int query(int k,int l,int r,int x,int y){
- if (x<=l&&r<=y){
- return tree[k];
- }
- if (lazy[k]!=1<<30) pushdown(k);
- int qwq=1<<30,mid=l+r>>1;
- if (x<=mid) qwq=min(qwq,query(k<<1,l,mid,x,y));
- if (mid<y) qwq=min(qwq,query(k<<1|1,mid+1,r,x,y));
- return qwq;
- }
- void solve(int x,int y,int z){
- while (top[x]!=top[y]){
- if (dep[top[x]]<dep[top[y]]) x^=y^=x^=y;
- modify(1,1,n,dfn[top[x]],dfn[x],z);
- x=fa[top[x]];
- }
- if (dep[x]<dep[y]) x^=y^=x^=y;
- modify(1,1,n,dfn[y]+1,dfn[x],z);
- }
- int main(){
- memset (son,-1,sizeof (son));
- read(n);read(m);
- for (register int i=1;i<n;++i){
- read(x);read(y);
- add(x,y,i);add(y,x,i);
- }
- dfs1(1,0);
- dfs2(1,1);
- build(1,1,n);
- for (register int i=1;i<=m;++i){
- read(x);read(y);read(z);
- solve(x,y,z);
- }
- for (register int i=2;i<=n;++i){
- idw[idn[i]]=i;
- }
- for (register int i=1;i<n;++i){
- int ans=query(1,1,n,dfn[idw[i]],dfn[idw[i]]);
- if (ans==1<<30) printf ("-1\n");
- else write(ans),EL;
- }
- return 0;
- }
- template<class T1>void read(T1 &r_e_a_d){
- T1 k=0;
- char ch=getchar();
- int flag=1;
- while(!isNum(ch)){
- if(ch=='-'){
- flag=-1;
- }
- ch=getchar();
- }
- while(isNum(ch)){
- k=((k<<1)+(k<<3)+ch-'0');
- ch=getchar();
- }
- r_e_a_d=flag*k;
- }
- template<class T1>void write(T1 w_r_i_t_e){
- if(w_r_i_t_e<0){
- putchar('-');
- write(-w_r_i_t_e);
- }else{
- if(w_r_i_t_e<10){
- putchar(w_r_i_t_e+'0');
- }else{
- write(w_r_i_t_e/10);
- putchar((w_r_i_t_e%10)+'0');
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3037241.html