程式師世界 >> 編程語言 >> 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]