3 条题解

  • 3
    @ 2026-6-14 0:14:42 

    // 最近公共祖先+树链剖分+数状数组
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=100010;
int idx=1,h[N],to[N<<1],ww[N<<1],ne[N<<1],del;
void add(int x,int y,int z){
  to[++idx]=y;ww[idx]=z;ne[idx]=h[x];h[x]=idx;
}
struct node{
  int x,y,z,id; //给每一条边编号
}e[N];
int n,m;
int dfn[N],siz[N],dep[N],son[N],fa[N],top[N];
ll d[N];
bool vis[N];

void dfs1(int x,int f){ //树链剖分 更新dep,fa,son,siz,d,e
  dep[x]=dep[f]+1; fa[x]=f; siz[x]=1;
  for(int i=h[x]; i; i=ne[i]){
    int y=to[i];
    if(y==f) continue;
    if(vis[y]){del=i>>1; continue;} //del记录那条断环边
    vis[y]=true;
    e[i>>1].id=i; //记录树边的编号i/2
    d[y]=d[x]+ww[i]; //d:记录y点到根的距离
    dfs1(y,x);
    siz[x]+=siz[y];
    if(siz[y]>siz[son[x]]) son[x]=y;
  }
}
void dfs2(int x,int t){ //树链剖分 更新dfn,top
  dfn[x]=++dfn[0]; //dfs序,用于BIT的下标
  top[x]=t;
  if(son[x]) dfs2(son[x],t); //搜重儿子
  for(int i=h[x]; i; i=ne[i]){
    int y=to[i];
    if(y==fa[x]||y==son[x]||
       y==e[del].x&&x==e[del].y||
       y==e[del].y&&x==e[del].x) continue; //排除断环边
    dfs2(y,y); //搜轻儿子
  }
}
int lca(int x,int y){ //求lca
  while(top[x]!=top[y]){
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    x=fa[top[x]];
  }
  return dep[x]>dep[y]?y:x;
}

struct BIT{ //数状数组
  ll s[N];
  void upd(int x,int C){ //点更新
    for(;x<=n;x+=x&-x) s[x]+=C;
  }
  void upd(int x,int y,int C){ //差分更新
    upd(x,C); upd(y+1,-C);
  }
  void change(int u,int C){ //区间更新
    upd(dfn[u], dfn[u]+siz[u]-1, C);
  }
  ll ask(int x){ //前缀和
    ll sum=0;
    for(;x;x-=x&-x) sum+=s[x];
    return sum;
  }
  ll dis(int u,int v){ //两点之间的距离
    return ask(dfn[u])+ask(dfn[v])-2*ask(dfn[lca(u,v)]);
  }
}B;

int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n>>m;
  for(int i=1,x,y,z; i<=n; i++){
    cin>>x>>y>>z;
    add(x,y,z); add(y,x,z);
    e[i]={x,y,z,0};
  }
  
  vis[1]=true; //标记访问1
  dfs1(1,0);
  dfs2(1,1); //树链剖分
  for(int i=1; i<=n; i++) B.upd(dfn[i],dfn[i],d[i]); //初始化BIT
  for(int op,x,y;m--;){
    cin>>op>>x>>y;
    if(op==1){
      if(x==del){
        e[x].z=y; //对断环边只更新边权
        continue;
      }
      int dy=y-e[x].z; //把修改的边权转化为增加量
      e[x].z=y;        //记录新边权
      int v=to[e[x].id]; //第x条边的终点
      B.change(v,dy); //v子树增加点权
    }
    else{
      ll d1=B.dis(x,y);
      ll d2=B.dis(x,e[del].x)+B.dis(y,e[del].y)+e[del].z;
      ll d3=B.dis(x,e[del].y)+B.dis(y,e[del].x)+e[del].z;
      cout<<min({d1,d2,d3})<<'\n';
    }
  }
}
    • 2
      @ 2026-6-14 9:45:57 
      #include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node1{int x,y,c;}e[N];
vector<int>G[N];
int fa[N],son[N],dep[N],siz[N];
void dfs(int x,int f)
{
	fa[x]=f,dep[x]=dep[f]+1;siz[x]=1,son[x]=0;
	for(int y:G[x])if(y!=f)
	{
		dfs(y,x);
		siz[x]+=siz[y];
		if(siz[son[x]]<=siz[y])son[x]=y;
	}
}
int tsp,dfn[N],_dfn[N],top[N];
void dfs1(int x,int tp)
{
	dfn[x]=++tsp,_dfn[tsp]=x;top[x]=tp;
	if(son[x]>0)dfs1(son[x],tp);
	for(int y:G[x])if(y!=fa[x]&&y!=son[x])dfs1(y,y);
}
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
struct node{int l,r,s;}tr[N<<2];
int a[N];
void push(int x){tr[x].s=tr[lc(x)].s+tr[rc(x)].s;}
void bt(int x,int l,int r)
{
	tr[x]={l,r,0};
	if(l==r){tr[x].s=a[_dfn[l]];return;}
	int m=(l+r)/2;
	bt(lc(x),l,m),bt(rc(x),m+1,r);
	push(x);
}
void change(int x,int f,int k)
{
	if(f<tr[x].l||f>tr[x].r)return;
	if(tr[x].l==tr[x].r){tr[x].s=k;return;}
	change(lc(x),f,k),change(rc(x),f,k);
	push(x); 
}
int query(int x,int l,int r)
{
	if(tr[x].l>r||tr[x].r<l)return 0;
	if(l<=tr[x].l&&tr[x].r<=r)return tr[x].s;
	return query(lc(x),l,r)+query(rc(x),l,r);
}
int getdis(int x,int y)
{
	int ret=0;
	for(;top[x]!=top[y];x=fa[top[x]])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ret+=query(1,dfn[top[x]],dfn[x]);
	}
	if(dep[x]>dep[y])swap(x,y);
	ret+=query(1,dfn[x]+1,dfn[y]);
	return ret;
}
int ffa[N],epos;
int findfa(int x){return ffa[x]==x?ffa[x]:ffa[x]=findfa(ffa[x]);}
signed main()
{
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)ffa[i]=i;
	for(int i=1,x,y,c;i<=n;i++)
	{
		cin>>x>>y>>c;e[i]={x,y,c};
		int tx=findfa(x),ty=findfa(y);
		if(tx==ty){epos=i;continue;}
		ffa[tx]=ty;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);
	tsp=0;dfs1(1,1);
	for(int i=1;i<=n;i++)if(epos!=i)
		if(dep[e[i].x]>dep[e[i].y])swap(e[i].x,e[i].y);
	for(int i=1;i<=n;i++)if(epos!=i)a[e[i].y]=e[i].c;
	bt(1,1,tsp);
	while(q--)
	{
		int op,x,y;cin>>op>>x>>y;
		if(op==1)
		{
			if(x==epos)e[epos].c=y;
			else change(1,dfn[e[x].y],y);	
		}
		else
		{
			int dis1=getdis(x,e[epos].y)+getdis(y,e[epos].x)+e[epos].c,dis2=getdis(x,e[epos].x)+getdis(y,e[epos].y)+e[epos].c;
			cout<<min({getdis(x,y),dis1,dis2})<<'\n';
		}
	}
	return 0;
}
      • 0
        @ 2026-6-14 14:14:27 
        #include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define N 1000010
int n,q;
vector<PII>G[N];
struct edge{
	int x,y,w,son;
}e[N];int bk,tp1,tp2,len;
int fa[N];
int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
void init(){
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++){
		int x=e[i].x,y=e[i].y;
		int tx=findfa(x),ty=findfa(y);
		if(tx==ty){
			bk=i,tp1=x,tp2=y,len=e[i].w;
			return;
		}
		fa[tx]=ty;
	}
}

int a[N];
int D,dep[N],siz[N],son[N];
void dfs(int x,int xfa){
	fa[x]=xfa;dep[x]=dep[xfa]+1,siz[x]=1,son[x]=-1;
	for(auto i:G[x])if(i.fi!=xfa){
		int y=i.fi,id=i.se;
		a[y]=e[id].w;
		e[id].son=y;
		dfs(y,x);
		siz[x]+=siz[y];
		if(son[x]||siz[son[x]]<siz[y])son[x]=y;
	}
}
int tsp,dfn[N],_dfn[N],top[N];
void dfs2(int x,int tp){
	dfn[x]=++tsp,_dfn[tsp]=x,top[x]=tp;
	if(son[x]>0)dfs2(son[x],tp);
	for(auto i:G[x])if(i.fi!=fa[x]&&i.fi!=son[x])
		dfs2(i.fi,i.fi);
}

#define lb(x) (x&-x)
int tre[N];
void add(int x,int k){for(;x<=n;x+=lb(x))tre[x]+=k;}
int getsum(int x){int res=0;for(;x;x-=lb(x))res+=tre[x];return res;}

int LCA(int x,int y){
	for(;top[x]!=top[y];x=fa[top[x]])if(dep[top[x]]<dep[top[y]])swap(x,y);
	return dep[x]<dep[y]?x:y;
}
int DIS(int x,int y){
	int lca=LCA(x,y);
	return getsum(dfn[x])+getsum(dfn[y])-2*getsum(dfn[lca]);
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>e[i].x>>e[i].y>>e[i].w;
	}
	
	init();
	
	for(int i=1;i<=n;i++)if(i!=bk){
		int x=e[i].x,y=e[i].y;
		G[x].push_back({y,i});
		G[y].push_back({x,i});
	}
	
	D=log2(n);tsp=0;
	dfs(tp1,0);
	dfs2(tp1,tp1);
	
	for(int i=1;i<=n;i++)add(dfn[i],a[i]),add(dfn[i]+siz[i],-a[i]);
	while(q--){
		int op,x,y;cin>>op>>x>>y;
		if(op==1){
			if(x==bk){
				len=y;
				continue;
			}
			int id=e[x].son;
			add(dfn[id],-a[id]);
			add(dfn[id]+siz[id],a[id]);
			a[id]=y;
			add(dfn[id],y);
			add(dfn[id]+siz[id],-y);
		}
		else{
			cout<<min({DIS(x,y),DIS(x,tp1)+len+DIS(tp2,y),DIS(x,tp2)+len+DIS(tp1,y)})<<'\n';
		}
	}
	
	return 0;
}
        • 1

        D157 最近公共祖先+树链剖分+数状数组 最短距离

        信息

        ID
        12485
        时间
        1000ms
        内存
        128MiB
        难度
        7
        标签
        递交数
        47
        已通过
        11
        上传者
        1. Language
        2. 兼容模式
        3. 主题
        3. Worker 0, 6ms
        4. Powered by Hydro v5.0.1 Community