题解 P8331【[ZJOI2022] 简单题】

xtx1092515503 · 2022-05-06 21:14:00 · 题解

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

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

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

膜拜赛时写出来的神仙。

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

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

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

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

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

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

点双是环。显然存在赋值方案。
点双是环上连一条链。
```
  ----w1----
 /          \
S-----w2-----T
 \          /
  ----w3----
```
即这样的东西。

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

不仅如此，假如点双由以 S,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)
但是当我们把它抵消一下的时候，就会发现其等价于
w_5+w_6=0
这个式子。

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

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

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

故点双中只要存在平行边，就不合法。就算平行边的端点之一退化在了一起，依照上式其亦不合法。
点双拥有两条交叉边。
```
------w1-------
|             |
A--w3---   ---B
|      |   |  |
w5 -w4-+---- w6
|  |   |      |
C---   |------D
|             |
------w4-------
```
（上图中的 + 仅表示两条边交叉了，不表示在该处存在节点）

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

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

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

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

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

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

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

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

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

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

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

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

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

考虑如何求出二元组。

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

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

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

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

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

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

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

建圆方树是显然线性的。

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

首先求二元组的过程是可以线性预处理、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;
}