loj2587 「APIO2018」铁人两项[圆方树+树形DP]

主要卡在一个结论上。。关于点双有一个常用结论，也经常作为在圆方树/简单路径上的良好性质，对于任意点双内互不相同的三点$s,c,t$，都存在简单路径$s\to c\to t$，证明不会。可以参见clz博客。。我就是跟着他学的

然后就好办了，转化为树上两点计经过点双内所有点个数，然后赋权后变为统计两两圆点对的路径权值和，这个就是一个树形DP，统计每个点作为圆点或者方点被所有路径经过多少次，加入答案。。

还是比较裸的，因为重点还在于这个很多题都出现到的点双的简单路径的性质。。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define mst(x) memset(x,0,sizeof x)

 #define dbg(x) cerr << #x << " = " << x <<endl

 #define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=1e5+;

 struct thxorz{

     int head[N<<],nxt[N<<],to[N<<],tot;

     inline void add(int x,int y){

         to[++tot]=y,nxt[tot]=head[x],head[x]=tot;

         to[++tot]=x,nxt[tot]=head[y],head[y]=tot;

     }

 }G1,G2;

 int n,m;

 ll ans;

 int val[N<<],siz[N<<],cnt,Siz;

 int dfn[N],low[N],stk[N],top,tim;

 #define y G1.to[j]

 void tarjan(int x){

     dfn[x]=low[x]=++tim,stk[++top]=x,++Siz;

     for(register int j=G1.head[x];j;j=G1.nxt[j]){

         if(!dfn[y]){

             tarjan(y),MIN(low[x],low[y]);

             if(low[y]==dfn[x]){

                 int tmp,sum=;++cnt;

                 do tmp=stk[top--],G2.add(cnt,tmp),val[tmp]=-,++sum;while(tmp^y);

                 G2.add(cnt,x),val[x]=-;val[cnt]=++sum;

             }

         }

         else MIN(low[x],dfn[y]);

     }

 }

 #undef y

 #define y G2.to[j]

 void dp(int x,int fa){

     int d=x<=n;siz[x]=d;

     for(register int j=G2.head[x];j;j=G2.nxt[j])if(y^fa){

         dp(y,x),siz[x]+=siz[y];

         ans+=siz[y]*1ll*(Siz-siz[y])*val[x];

     }

     ans+=d*(Siz-)*1ll*val[x]+(Siz-siz[x])*1ll*siz[x]*val[x];

 }

 #undef y

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     read(n),read(m);cnt=n;

     for(register int i=,x,y;i<=m;++i)read(x),read(y),G1.add(x,y);

     for(register int i=;i<=n;++i)if(!dfn[i]){

         Siz=top=;tarjan(i),dp(i,);

     }

     printf("%lld\n",ans);

     return ;

 }

总结：图上简单路径题多半和点双有关系