Description

给一个包含\(n\)个点，\(m\)条边的无向连通图。从顶点\(1\)出发，往其余所有点分别走一次并返回。

往某一个点走时，选择总长度最短的路径走。若有多条长度最短的路径，则选择经过的顶点序列字典序最小的那条路径(如路径\(A\)为\(1,32,11\)，路径\(B\)为\(1,3,2,11\)，路径B字典序较小。注意是序列的字典序的最小，而非路径中节点编号相连的字符串字典序最小)。到达该点后按原路返回，然后往其他点走，直到所有点都走过。

可以知道，经过的边会构成一棵最短路径树。请问，在这棵最短路径树上，最长的包含K个点的简单路径长度为多长？长度为该最长长度的不同路径有多少条？

这里的简单路径是指：对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同，点\(A\)到点\(B\)的路径和点\(B\)到点\(A\)视为同一条路径。

Solution

强行二合一题目

虽然用点分治可以很轻松的A过

但是还是想用长链剖分来做

首先\(dijkstra+dfs\)求出题目中所要求的那棵最短路树

考虑树dp

\(f[x][i]\)表示从\(x\)往下\(j\)长度链的最大距离

\(g[x][i]\)表示满足最大距离的链的数量

对于长链剖分的重儿子，直接继承它的答案

至于怎么继承，就不说了，不过\(O(1)\)继承确实是长链剖分处理树形\(dp\)的核心呢

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)>(b)?(b):(a))#define reg registerinline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}const int MN=3e4+5,MM=6e4+5;int n,m,K;struct edge{    int to,w,nex;    bool operator <(const edge&o)const{return to
     
      
       G[MN];inline void ins_(int x,int y,int w){    G[x].push_back((edge){y,w,0});    G[y].push_back((edge){x,w,0});}int hr[MN],Hr[MN],en;inline void ins(int x,int y,int w){e[++en]=(edge){y,w,hr[x]};hr[x]=en;}int dis[MN];class dijkstra{    #define nN 32768    #define inf 0x3f3f3f3f    struct node{int x,f;}t[nN<<1];    inline node Min(const node&o,const node&oo){return o.x
       
        >=1;)t[k]=Min(t[k<<1],t[k<<1|1]);}    public:        inline void solve()        {            reg int i,x;            for(i=1;i
        
         <<1;++i) t[i].x=inf;            for(i=1;i<=n;++i) dis[t[i+nN].f=i]=inf;            for(rw(1,dis[1]=0);t[1].x!=inf;)            {                rw(x=t[1].f,inf);                for(i=0;i
         
          dis[x]+G[x][i].w) rw(G[x][i].to,dis[G[x][i].to]=dis[x]+G[x][i].w); } }}dij;bool vis[MN];void dfs1(int x){ for(reg int i=0;i
          
           =len[mx[x]]) mx[x]=e[i].to,w[x]=e[i].w; if(len[e[i].to]+1>len[x]) len[x]=len[e[i].to]+1; }}int ans1,ans2,f[MN],g[MN],ind,siz[MN],dfn[MN];void C(int x,int y){ if(x>ans1) ans1=x,ans2=y; else if(x==ans1) ans2+=y;}void solve(int x){ reg int i,j,pos=dfn[x]=++ind; if(mx[x]) solve(mx[x]),siz[pos]=siz[pos+1]+w[x]; f[pos]=-siz[pos];g[pos]=1; if(K<=len[x]) C(f[pos+K]+siz[pos],g[pos+K]); for(i=hr[x];i;i=e[i].nex)if(e[i].to!=mx[x]) { solve(e[i].to);reg int pv=dfn[e[i].to]; for(j=0;j<=len[e[i].to];++j)if(j+1<=K&&K-j-1<=len[x]) C(siz[pv]+f[pv+j]+siz[pos]+f[pos+K-1-j]+e[i].w,g[pv+j]*g[pos+K-1-j]); for(j=0;j<=len[e[i].to];++j) { int tmp=siz[pv]+f[pv+j]+e[i].w-siz[pos]; if(tmp>f[pos+j+1]) f[pos+j+1]=tmp,g[pos+j+1]=g[pv+j]; else if(tmp==f[pos+j+1]) g[pos+j+1]+=g[pv+j]; } }}int main(){ n=read(),m=read(),K=read()-1; reg int i,x,y; while(m--) x=read(),y=read(),ins_(x,y,read()); for(i=1;i<=n;++i) std::sort(G[i].begin(),G[i].end()); dij.solve();dfs1(1);dfs2(1); ans1=-inf;memset(f,-1,sizeof f);solve(1); printf("%d %d\n",ans1,ans2); return 0;}
          
         
        
       
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！