程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 3611: [Heoi2014]大工程|樹形DP|虛樹

3611: [Heoi2014]大工程|樹形DP|虛樹

編輯:C++入門知識

3611: [Heoi2014]大工程|樹形DP|虛樹


構建出虛樹然後DP統計答案
自己寫的DP太傻QAQ,各種WA
膜了一發PoPoQQQ大爺的DP方法
mxdis,mndis分別表示到當前點最近和最遠的被選出來的點的距離
mx,mn分別表示在以當前點為根的情況下距離最遠的兩點的距離和距離最近的兩點的距離。
sum表示在以當前點為根的子樹中,所有關鍵的到當前點的距離之和
c數組表示以當前點為根的子樹中,關鍵點的個數
然後我用了個時間戳來標記關鍵點

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x7FFFFFFF
#define ll long long
#define N 1000005
using namespace std;
int sc()
{
    int i=0,f=1; char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
    return i*f;
}
ll mx[N],mn[N],mn_dis[N],mx_dis[N],c[N],sum[N],ans;
int Head[N],Nxt[N],Lst[N];
int a[N],st[N],tim[N];
int size[N],deep[N],fa[N],S[N],top[N];
int head[N],lst[N<<1],nxt[N<<1],v[N<<1];
int n,tot,cnt,Tot,TI;
void Insert(int x,int y)
{
    Lst[++Tot]=y;Nxt[Tot]=Head[x];Head[x]=Tot;
}
void insert(int x,int y)
{
    lst[++tot]=y;nxt[tot]=head[x];head[x]=tot;
    lst[++tot]=x;nxt[tot]=head[y];head[y]=tot;
}
void dfs(int x,int f)
{
    size[x]=1;
    for(int i=head[x];i;i=nxt[i])
        if(lst[i]!=f)
        {
            deep[lst[i]]=deep[x]+1;
            fa[lst[i]]=x;
            dfs(lst[i],x);
            size[x]+=size[lst[i]];
        }
}
void _dfs(int x,int htp)
{
    int k=0;top[x]=htp;S[x]=++cnt;
    for(int i=head[x];i;i=nxt[i])
        if(lst[i]!=fa[x]&&size[lst[i]]>size[k])k=lst[i];
    if(!k)return;_dfs(k,htp);
    for(int i=head[x];i;i=nxt[i])
        if(lst[i]!=k&&lst[i]!=fa[x])
            _dfs(lst[i],lst[i]);
}
int Lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]1&&deep[f]

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved