1 条题解

  • 0
    @ 2025-8-24 22:38:05

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar xtx1092515503
    Mathematics compares the most diverse phenomena, and discovers the secret analogies which unite them. @Joseph Fourier

    搬运于2025-08-24 22:38:05，当前版本为作者最后更新于2022-05-06 21:14:00，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    就 ZJOI D1 T3 来言，这题事实上并不能说很难（至少我觉得联合省选 D1 T3 要比这题难）。

    本题也并没有过于难写，但是感觉问题主要还是在于大样例只有仙人掌。

    VP 的时候成功码完了正解，但是赛后一测发现只有四十分。听说有不止一个人和我一样一百挂成四十了。

    膜拜赛时写出来的神仙。

    这个简单路径求和，想想看可能是个 NP Hard 问题。

    怎么办呢？题目中说 初始保证图上任意两个简单环的边权和相等，然后修改了边权。

    换句话说，本题的图满足 存在一种重新赋值的方案，使得图上任意两个简单环的边权和相等。

    谁都能看出来这个性质是解决本题的关键。我们来分析一下吧！

    首先，本题显然是关于点双独立的：如果每个点双都存在一种赋值的方案，则显然整张图亦存在一种赋值方案。

    然后我们手玩几个比较 simple 的点双吧。以下的点双中所有边都可以是一堆点连成的链，这样两个点间就可以出现重边（因为其对应了不同的链）。

    • 点双是环。显然存在赋值方案。

    • 点双是环上连一条链。

        ----w1----
 /          \
S-----w2-----T
 \          /
  ----w3----

      即这样的东西。

      我们发现，只需赋值使得 w1=w2=w3w_1=w_2=w_3，这个情形就是合法的：任意简单环都包含恰两条链，则显然它们的权值都相等。

      不仅如此，假如点双由以 S,TS,T 为端点的若干条链构成，则只需令所有链中边权和全都相等，则显然这个情形亦是合法的。

      我们发现这个东西神似 细胞分裂中期时，纺锤体和纺锤丝的结构。

      也有的人把它称作 杏仁 或者 打蛋器。

      不管它叫什么，这种结构反正是一种合法结构。

    • 点双拥有两条平行边。

      ------w1-------
|             |
A-----w2------B
|             |
w5           w6
|             |
C-----w3------D
|             |
------w4-------

      即上图。

      我们有如下几个环：

      $$\begin{cases} w_1+w_2\\ w_3+w_4\\ w_1+w_5+w_3+w_6\\ w_2+w_5+w_4+w_6\\ w_1+w_5+w_4+w_6\\ w_2+w_3+w_5+w_6 \end{cases} $$

      我们要存在一组排列方式，使得这六个式子全都相等。

      假如其全部相等，则下式势必成立：

      $$(w_1+w_2)+(w_3+w_4)=(w_1+w_5+w_4+w_6)+(w_2+w_3+w_5+w_6) $$

      但是当我们把它抵消一下的时候，就会发现其等价于

      w5+w6=0w_5+w_6=0

      这个式子。

      注意到边权全部为正。故此式不可能成立，也即这种情形不可能有解。

      但是我们可以稍微修改一下定义：我们令一组 ww 中可能不含任何边，也即 ww 两侧的点可能重合。这时我们发现，只有 w5=w6=0w_5=w_6=0 才是合法条件。

      注意到 w5=w6=0w_5=w_6=0 意味着 A,CA,C 重合，B,DB,D 重合，整张图退化成杏仁。

      故点双中只要存在平行边，就不合法。就算平行边的端点之一退化在了一起，依照上式其亦不合法。

    • 点双拥有两条交叉边。

      ------w1-------
|             |
A--w3---   ---B
|      |   |  |
w5 -w4-+---- w6
|  |   |      |
C---   |------D
|             |
------w4-------

      （上图中的 + 仅表示两条边交叉了，不表示在该处存在节点）

      仍可仿照之前的证明，导出若该式成立则边权必然为零，留给读者自证。

    我们是不是已经考虑了所有类型的点双呢？

    考虑往杏仁上随便再添一条边，就会发现其要么与一条边平行，要么与一条边相交，总之不合法。而当我们往环上添一条边后，其必然会得到杏仁。

    也即，任意一种往环上加边的流程必然是 环->杏仁->不合法。

    这就表明所有合法的态仅可能是杏仁态，而我们已经证明只有杏仁态合法。

    介于我们已经在关于点双考虑，所以我们自然想着要去建一棵 圆方树。

    原图中 S→TS\to T 的路径在圆方树中是一条圆点方点交替的路径。其中，每个圆点都是原图中的必经之点（因为是割点）。

    于是，我们就可以把路径分段：对于每对在路径上相邻的圆点，我们记一个二元组 (num,sum)(num,sum) 表示这两个点间有 numnum 条路径，其路径和是 sumsum。二元组间可以简单合并。

    于是我们现在仅需求出路径上相邻圆点的二元组。

    我们考虑把圆方树上 S→TS\to T 的路径拆成 S→LCAS\to LCA 以及 LCA→TLCA\to T 两段。每一段中，都是不断跳父亲的过程。

    注意到一个圆点的后继节点是 其在圆方树上的二级父亲。于是我们预处理出所有点与其在圆方树上二级父亲间的二元组，共计 O(n)O(n) 个。则剩下的就仅仅是一次路径查询了。

    注意到 LCA 可能是方点，此时我们还要再额外考虑两段路径顶的圆点间的二元组，但这对于每次询问至多只需考虑一个。

    则我们若能快速求出两个圆点间的二元组，就可以简单回答询问。

    考虑如何求出二元组。

    这涉及到分类讨论：我们需要分询问涉及到的两个圆点是否在杏仁中的同一条链上，对两种情形分开考虑。

    我们首先来考虑在同一条链的情形。假如询问中的某个点是杏仁的“端点”或者细胞分裂模型中的“纺锤体”，也可以被归入该类型。

    令 A,BA,B 是杏仁的端点，SS 是杏仁中链数，RR 是杏仁中所有边的权值和，x,yx,y 两点是询问的点。

    不妨令 xx 离 AA 更近，则 yy 离 BB 更近。则我们可以简单得出，同一条链的时候，有 num=S,sum=R+(S−2)(dis(A,x)+dis(B,y))num=S,sum=R+(S-2)\Big(dis(A,x)+dis(B,y)\Big)。

    同理，在不同链的时候，令 sx,sys_x,s_y 为两个点所在链的权值和，可以简单得出有 num=2(S−1),sum=2R+(S−3)(sx+sy)num=2(S-1),sum=2R+(S-3)(s_x+s_y)。

    这些信息都是可以简单维护的。

    最后，我们来分析一下复杂度。

    建圆方树是显然线性的。

    线性对数是显然可以简单实现的。能不能进一步优化呢？

    首先求二元组的过程是可以线性预处理、O(1)O(1) 查询的。

    然后就是路径信息查询了。求 LCA 可以简单离线 Tarjan 做到线性反阿克曼，也可以大力四毛子做到线性。路径信息显然可以倍增做到对数，但是注意到二元组具有可减性，做减法时只需要求逆，用离线线性求逆元的科技即可做到线性。

    总复杂度是可以做到线性的，尽管毫无实际意义。

    代码是线性对数的。

    #include<bits/stdc++.h>
using namespace std;
const int N=500100;
const int M=640100;
typedef long long ll;
int n,m,q;
const int mod=998244353;
namespace FIFO{
void read(int&x){
	x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
void print(int x){if(x>=10)print(x/10);putchar('0'+x%10);}
}using namespace FIFO;
namespace Tre{
struct node{int to,next,val;}edge[M<<1];
int cnt;
vector<int>v[N<<1],id[N<<1],d[N<<1],chn[N];
int A[N<<1],B[N<<1],S[N<<1],R[N<<1];
vector<ll>disa[N],disb[N];
void ae(int k,int x,int y,int z){
	// printf("AE:%d,%d,%d,%d\n",k,x,y,z);
	x=id[x][lower_bound(v[x].begin(),v[x].end(),k)-v[x].begin()];
	y=id[y][lower_bound(v[y].begin(),v[y].end(),k)-v[y].begin()];
	// printf("%d,%d\n",x,y);
	edge[cnt].next=id[k][x],edge[cnt].to=y,edge[cnt].val=z,id[k][x]=cnt++;
	edge[cnt].next=id[k][y],edge[cnt].to=x,edge[cnt].val=z,id[k][y]=cnt++;
	d[k][x]++,d[k][y]++;
}
struct dat{
int num,sum;
dat(){num=sum=0;}
dat(int _n,int _s){num=_n,sum=_s;}
void print()const{printf("(%d,%d)",num,sum);}
friend dat operator*(const dat&u,const dat&v){
	return dat(1ll*u.num*v.num%mod,(1ll*u.num*v.sum+1ll*u.sum*v.num)%mod);
}
}jum[N][20];
int anc[N<<1][20],dep[N<<1],c;
void ae(int x,int y){v[x].push_back(y),id[x].push_back(v[y].size()),v[y].push_back(x);}
void dfs(int x,int fa){
	// printf("%d->%d\n",fa,x);
	anc[x][0]=fa;for(int i=1;i<20;i++)anc[x][i]=anc[anc[x][i-1]][i-1];dep[x]=dep[fa]+1;
	for(auto y:v[x])if(y!=fa)dfs(y,x);
}
int LCA(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	for(int i=19;i>=0;i--)if(dep[x]<=dep[y]-(1<<i))y=anc[y][i];
	if(x==y)return x;
	for(int i=19;i>=0;i--)if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
	return anc[x][0];
}
void ae(int x,int y,int z){
	if(anc[x][0]==anc[y][0])ae(anc[x][0],x,y,z);
	else if(anc[x][1]==y)ae(anc[x][0],x,y,z);
	else if(anc[y][1]==x)ae(anc[y][0],x,y,z);
}
dat calc(int k,int x,int y){
	int _x=lower_bound(v[x].begin(),v[x].end(),k)-v[x].begin();
	int _y=lower_bound(v[y].begin(),v[y].end(),k)-v[y].begin();
//	printf("%d:%d,%d,%d,%d,%d,%d,%d\n",x,v[x].size(),id[x].size(),chn[x].size(),disa[x].size(),disb[x].size(),d[x].size(),_x);
//	printf("%d:%d,%d,%d,%d,%d,%d,%d\n",y,v[y].size(),id[y].size(),chn[y].size(),disa[y].size(),disb[y].size(),d[y].size(),_y);
	int X=id[x][_x];
	int Y=id[y][_y];
	if(X!=A[k]&&Y!=A[k]&&X!=B[k]&&Y!=B[k]&&chn[x][_x]!=chn[y][_y])
	return dat((S[k]-1)<<1,((R[k]<<1)+(disa[x][_x]+disb[x][_x]+disa[y][_y]+disb[y][_y])%mod*(S[k]+mod-3))%mod);
	ll xa,xb,ya,yb;
	if(X==A[k])xa=0,xb=0x3f3f3f3f3f3f3f3f;
	else if(X==B[k])xa=0x3f3f3f3f3f3f3f3f,xb=0;
	else xa=disa[x][_x],xb=disb[x][_x];
	if(Y==A[k])ya=0,yb=0x3f3f3f3f3f3f3f3f;
	else if(Y==B[k])ya=0x3f3f3f3f3f3f3f3f,yb=0;
	else ya=disa[y][_y],yb=disb[y][_y];
	ll _a,_b;
	if(xa>ya)_a=ya,_b=xb;else _a=xa,_b=yb;
	return dat(S[k],(R[k]+(_a+_b)%mod*(S[k]+mod-2))%mod);
}
int calc(int x,int y){
	int z=LCA(x,y);
	// printf("%d(%d,%d)\n",z,x,y);
	dat res(1,0);
	for(int i=19;i;i--)if(dep[z]<=dep[x]-(1<<i))res=res*jum[x][i-1],x=anc[x][i];
	for(int i=19;i;i--)if(dep[z]<=dep[y]-(1<<i))res=res*jum[y][i-1],y=anc[y][i];
	if(x==z&&y==z)return res.sum;
	return (res*calc(z,x,y)).sum;
}
ll walk(int k,int x,int fr,ll ds){
	for(int i=id[k][x],y;i!=-1;i=edge[i].next)if((y=edge[i].to)!=fr){
		disa[v[k][x]].push_back(ds);
		chn[v[k][x]].push_back(S[k]);
		if(y==B[k]){
			disb[v[k][x]].push_back(edge[i].val),R[k]=(ds+edge[i].val+R[k])%mod;
			return edge[i].val;
		}
		ds=walk(k,y,x,ds+edge[i].val)+edge[i].val;
		disb[v[k][x]].push_back(ds);
		return ds;
	}
	return 0;
}
void func(int k){
	A[k]=B[k]=-1;
	for(int i=0;i<d[k].size();i++){
		if(d[k][i]==2)continue;
		if(A[k]==-1)A[k]=i;else B[k]=i;
	}
	if(A[k]==-1&&B[k]==-1)A[k]=0,B[k]=1;
	// printf("FUNC:%d\n",k);
	// for(auto x:v[k])printf("%d ",x);puts("");
	// printf("%d %d\n",A[k],B[k]);
	chn[v[k][A[k]]].push_back(-1),disa[v[k][A[k]]].push_back(-1),disb[v[k][A[k]]].push_back(-1);
	chn[v[k][B[k]]].push_back(-1),disa[v[k][B[k]]].push_back(-1),disb[v[k][B[k]]].push_back(-1);
	for(int i=id[k][A[k]];i!=-1;i=edge[i].next){
		S[k]++;
		if(edge[i].to==B[k]){(R[k]+=edge[i].val)%=mod;continue;}
		walk(k,edge[i].to,A[k],edge[i].val);
	}
}
void init(){
	dfs(1,0);
//	for(int i=1;i<=n;i++)printf("%d %d\n",v[i].size(),id[i].size());
	// for(int i=1;i<=c;i++){printf("%d:",i);for(auto x:v[i])printf("%d ",x);puts("");}
	for(int i=n+1;i<=c;i++)id[i].resize(v[i].size(),-1),d[i].resize(v[i].size());
}
void tini(){
	for(int i=n+1;i<=c;i++)func(i);
	for(int i=2;i<=n;i++)jum[i][0]=calc(anc[i][0],anc[i][1],i);
	// for(int i=2;i<=n;i++)printf("%d:(%d,%d)\n",i,jum[i][0].num,jum[i][0].sum);
	for(int j=1;j<20;j++)for(int i=1;i<=n;i++)jum[i][j]=jum[i][j-1]*jum[anc[i][j]][j-1];
}
}
namespace Gra{
int dfn[N],low[N],tot,stk[N],tp,X[M],Y[M],Z[M];
vector<int>v[N];
void Tarjan(int x){
	dfn[x]=low[x]=++tot,stk[++tp]=x;
	for(auto y:v[x]){
		if(!dfn[y]){
			Tarjan(y),low[x]=min(low[x],low[y]);
			if(low[y]<dfn[x])continue;
			Tre::c++;
			int z;do z=stk[tp--],Tre::ae(z,Tre::c);while(z!=y);
			Tre::ae(x,Tre::c);
			// for(auto z:Tre::v[Tre::c])printf("%d ",z);puts("");
		}else low[x]=min(low[x],dfn[y]);
	}
}
void init(){
	for(int i=1;i<=m;i++)
		read(X[i]),read(Y[i]),read(Z[i]),v[X[i]].push_back(Y[i]),v[Y[i]].push_back(X[i]);
	// for(int i=1;i<=m;i++)printf("%d %d %d\n",X[i],Y[i],Z[i]);
	Tarjan(1);
	Tre::init();
	for(int i=1;i<=m;i++)Tre::ae(X[i],Y[i],Z[i]);
}
}
int main(){
	freopen("simple.in","r",stdin);
	freopen("simple.out","w",stdout);
	read(n),read(m),read(q),Tre::c=n;
	Gra::init();
	Tre::tini();
	for(int i=1,x,y;i<=q;i++)read(x),read(y),print(Tre::calc(x,y)),putchar('\n');
	return 0;
}
    • 1

    [ZJOI2022] 简单题

    信息

    ID
    7654
    时间
    6000ms
    内存
    1024MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 23ms