Processing math: 100%

BZOJ3743:[Coci2015]Kamp 树形dp

10 年前

思路:

首先发现如果根确定的话,我们要求的答案就是根和关键点们组成的虚树的边长之和的2倍减去根到所有关键点的距离最大值.

这个应该不难理解.

 

然后觉得虚树很难处理,就抛弃虚树,弄了一个繁琐至极的两遍dp.(这个我就不写是怎么dp的啦,大家应该都会.)

 

然后看到某个题解说最上面说的那个东西bfs就行.

如何呢?

一个关键的性质:树上距离一个点最远的点必定是直径的一端!这个想想很显然.

然后就简单了.

 

下面是我的傻叉dp:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define INF 1ll<<59
  
#define N 500010
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int c){static int q=1;end[q]=b,next[q]=head[a],head[a]=q,len[q++]=c;}
inline void make(int a,int b,int c){addedge(a,b,c),addedge(b,a,c);}
  
bool c[N];
  
long long max_dis[N],cnt[N],total_dis[N];
inline void dp1(int x,int fa){
    for(int j=head[x];j;j=next[j])if(end[j]!=fa)dp1(end[j],x);
    cnt[x]=c[x],max_dis[x]=c[x]?0:-INF,total_dis[x]=0;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        cnt[x]+=cnt[end[j]];
        max_dis[x]=max(max_dis[x],max_dis[end[j]]+len[j]);
        total_dis[x]+=total_dis[end[j]]+(cnt[end[j]]?1ll:0ll)*len[j];
    }
}
  
long long re[N];
long long seq[N],pre[N],suc[N],g[N];
inline void dp2(int x,int fa,int fadis){
    long long real_total_dis,real_max_dis;
    if(x==1)real_total_dis=total_dis[x],real_max_dis=max_dis[x];
    else{
        real_total_dis=total_dis[x]+total_dis[fa]+(cnt[fa]?1ll:0ll)*fadis;
        real_max_dis=max(max_dis[x],max_dis[fa]+fadis);
    }
    re[x]=real_total_dis*2-real_max_dis;
      
    int num=0;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa)seq[++num]=max_dis[end[j]]+len[j];
    pre[0]=suc[num+1]=-INF;
    for(int i=1;i<=num;++i)pre[i]=max(seq[i],pre[i-1]);
    for(int i=num;i>=1;--i)suc[i]=max(seq[i],suc[i+1]);
      
    num=0;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        ++num;
        g[end[j]]=max(pre[num-1],suc[num+1]);
    }
      
    int real_cnt=cnt[x];
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        total_dis[x]=real_total_dis-total_dis[end[j]];
        if(cnt[end[j]])total_dis[x]-=len[j];
        max_dis[x]=g[end[j]];
        if(x!=1)max_dis[x]=max(max_dis[x],max_dis[fa]+fadis);
        if(c[x])max_dis[x]=max(max_dis[x],0ll);
        cnt[x]=real_cnt-cnt[end[j]]+cnt[fa];
          
        dp2(end[j],x,len[j]);
    }
}
  
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    if(m==0){puts("0");return 0;}
    int a,b,x;
    for(i=1;i<n;++i)scanf("%d%d%d",&a,&b,&x),make(a,b,x);
      
    while(m--)scanf("%d",&x),c[x]=1;
    dp1(1,-1);
    dp2(1,-1,0);
      
    for(i=1;i<=n;++i)printf("%lld\n",re[i]);
    return 0;
}

Tags: 树形dp
Posted in BZOJ | 0 Comments

BZOJ3611: [Heoi2014]大工程 LCA单调性+树形dp

10 年前

思路:思路基本同上一道题.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define INF 0x1f1f1f1f
  
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
}
#define N 1000010
int Head[N],Next[N<<1],End[N<<1],Len[N<<1];
inline void addedge(int a,int b,int x){static int q=1;End[q]=b,Next[q]=Head[a],Head[a]=q,Len[q++]=x;}
inline void make(int a,int b,int x){addedge(a,b,x),addedge(b,a,x);}
  
int dfn[N],id,dep[N],pa[N][21];
inline bool cmp(const int&x,const int&y){return dfn[x]<dfn[y];}
inline void dfs(int x,int fa){
    dfn[x]=++id;
    for(int j=Head[x];j;j=Next[j])if(End[j]!=fa)dep[End[j]]=dep[x]+1,pa[End[j]][0]=x,dfs(End[j],x);
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
int getdis(int son,int Anc){
    //int r=0;for(int i=20;i>=0;--i)if(dep[pa[son][i]]>=dep[Anc])r+=w[son][i],son=pa[son][i];return r;
    return dep[son]-dep[Anc];
}
  
struct Array{
    int d[N],t[N],init;
    Array(){}
    Array(int _init):init(_init){}
    inline int ask(int x,int nowv){
        if(t[x]!=nowv)t[x]=nowv,d[x]=init;return d[x];
    }
    inline void modify(int x,int to,int nowv){
        t[x]=nowv,d[x]=to;
    }
    inline void maxi(int x,int to,int nowv){
        if(t[x]!=nowv)t[x]=nowv,d[x]=init;if(d[x]<to)d[x]=to;
    }
    inline void mini(int x,int to,int nowv){
        if(t[x]!=nowv)t[x]=nowv,d[x]=init;if(d[x]>to)d[x]=to;
    }
    inline void add(int x,int c,int nowv){
        if(t[x]!=nowv)t[x]=nowv,d[x]=init;d[x]+=c;
    }
};
  
int nowv;
struct Tree{
    Array h;int next[N],end[N],len[N],ind;
    inline void reset(){h.init=-1;ind=0;}
    inline void addedge(int a,int b){int q=ind++;end[q]=b,next[q]=h.ask(a,nowv),h.modify(a,q,nowv),len[q++]=getdis(b,a);}
}G;
  
int seq[N],siz,end;
  
int stk[N],top,Anc[N];
  
Array isimp(0),maxdep(-INF),mindep(INF),cnt(0);
long long tot;
int maxans,minans;
inline void mini(int&x,int y){if(x>y)x=y;}
inline void maxi(int&x,int y){if(x<y)x=y;}
void Solve(int x){
    for(int j=G.h.ask(x,nowv);j!=-1;j=G.next[j])Solve(G.end[j]),cnt.add(x,cnt.ask(G.end[j],nowv),nowv),tot+=(long long)G.len[j]*cnt.ask(G.end[j],nowv)*(siz-cnt.ask(G.end[j],nowv));
    if(isimp.ask(x,nowv))maxdep.modify(x,0,nowv),mindep.modify(x,0,nowv),cnt.add(x,1,nowv);
    for(int j=G.h.ask(x,nowv);j!=-1;j=G.next[j])
        mini(minans,mindep.ask(x,nowv)+mindep.ask(G.end[j],nowv)+G.len[j]),
        mindep.mini(x,mindep.ask(G.end[j],nowv)+G.len[j],nowv);
    for(int j=G.h.ask(x,nowv);j!=-1;j=G.next[j])
        maxi(maxans,maxdep.ask(x,nowv)+maxdep.ask(G.end[j],nowv)+G.len[j]),
        maxdep.maxi(x,maxdep.ask(G.end[j],nowv)+G.len[j],nowv);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    //freopen("tt.out","w",stdout);
    #endif
    using namespace Fio;
    int n;Get(n);
    register int i,j;int a,b;for(i=1;i<n;++i)Get(a),Get(b),make(a,b,1);
    dep[1]=1,dfs(1,-1);
    for(j=1;j<=20;++j)
        for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1];
    int Q;Get(Q);
    while(Q--){
        Get(siz);for(i=1;i<=siz;++i)Get(seq[i]);end=siz;sort(seq+1,seq+siz+1,cmp);
        ++nowv;for(i=1;i<=siz;++i)isimp.modify(seq[i],1,nowv);
        for(top=0,i=1;i<=siz;++i){
            if(!top)stk[++top]=seq[i];
            else{
                int Lca=lca(stk[top],seq[i]);Anc[seq[i]]=Lca;
                while(dep[stk[top]]>dep[Lca]){if(dep[stk[top-1]]<=dep[Lca])Anc[stk[top]]=Lca;--top;}
                if(Lca!=stk[top])Anc[Lca]=stk[top],seq[++end]=stk[++top]=Lca;
                stk[++top]=seq[i];
            }
        }
        sort(seq+1,seq+end+1,cmp);for(G.reset(),i=2;i<=end;++i)G.addedge(Anc[seq[i]],seq[i]);
        tot=0,minans=INF,maxans=-INF,Solve(seq[1]);
        printf("%lld %d %d\n",tot,minans,maxans);
    }
    return 0;
}

Tags: LCA单调性 树形DP
Posted in BZOJ | 0 Comments

BZOJ2286: [Sdoi2011]消耗战 LCA单调性+树形dp

10 年前

思路:

首先对于一次询问进行一次朴素的树形dp极为容易.不过这样需要O(n)的时间复杂度,这样总的时间复杂度为O(qn),无法通过.

我们能否对于一次询问,将时间复杂度限定至仅与关键点数有关呢?

 

我们考虑构造一个树结构,仅仅将关键点连接起来,并适当添加部分非关键点,我们如果在这样减缩后的树上做dp,就能使得复杂度只与关键点数有关.

我们利用一个单调栈维护树上的一条深度单调递增的链,当我们要添加的点与栈顶的点的lca深度小于栈顶时,我们不断弹栈并在这个过程中顺便维护此时树的形态.

容易发现,对于每次添加,至多在新树上添加一个点,因此新树的点数只与关键点线性相关.

 

接下来在新树上作朴素的树形dp就行了.

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc())&&c!='-');bool sign=c=='-';
        x=sign?0:c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
        if(sign)x=-x;
    }
    char buf[5000010],*o=buf;
    template<typename T>inline void print(T x){
        static int stk[100];int top=0;if(x<0)*o++='-',x=-x;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void Final(){fwrite(buf,1,o-buf,stdout);}
}
  
#define N 250010
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int x){
    static int q=1;end[q]=b,next[q]=head[a],len[q]=x,head[a]=q++;
}
inline void make(int a,int b,int x){addedge(a,b,x),addedge(b,a,x);}
  
int pa[N][21],w[N][21],dfn[N],id,dep[N];
void dfs(int x,int fa){
    dfn[x]=++id;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        dep[end[j]]=dep[x]+1,pa[end[j]][0]=x,w[end[j]][0]=len[j],dfs(end[j],x);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
long long calc(int son,int Anc){
    int res=100010;for(int i=20;i>=0;--i)if(dep[pa[son][i]]>=dep[Anc])res=min(res,w[son][i]),son=pa[son][i];return res;
}
  
int seq[N],siz;
  
inline bool cmp(const int&a,const int&b){return dfn[a]<dfn[b];}
  
int stk[N],top,Anc[N];
  
struct Array{
    long long sum[N];int t[N];
    inline void modify(int x,int add,int v){
        if(t[x]!=v)t[x]=v,sum[x]=0;sum[x]+=add;
    }
    inline long long ask(int x,int v){
        if(t[x]!=v)t[x]=v,sum[x]=0;return sum[x];
    }
}f,IsImp;int nowv;
  
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    using namespace Fio;
    int n;Fio::Get(n);
    register int i,j;int a,b,x;for(i=1;i<n;++i)Get(a),Get(b),Get(x),make(a,b,x);
    dep[1]=1,dfs(1,-1);
    for(j=1;j<=20;++j)
        for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1],w[i][j]=min(w[i][j-1],w[pa[i][j-1]][j-1]);
    int Q;Get(Q);
    while(Q--){
        Get(siz);for(i=1;i<=siz;++i)Get(seq[i]);++nowv;for(i=1;i<=siz;++i)IsImp.modify(seq[i],1,nowv);seq[++siz]=1;
        sort(seq+1,seq+siz+1,cmp);int end=siz;
        for(top=0,i=1;i<=siz;++i){
            if(!top)stk[++top]=seq[i];
            else{
                int Lca=lca(stk[top],seq[i]);Anc[seq[i]]=Lca;
                while(dep[stk[top]]>dep[Lca]){if(dep[stk[top-1]]<=dep[Lca])Anc[stk[top]]=Lca;--top;}
                if(stk[top]!=Lca)Anc[Lca]=stk[top],seq[++end]=stk[++top]=Lca;
                stk[++top]=seq[i];
            }
        }
        sort(seq+1,seq+end+1,cmp);
        //for(i=1;i<=siz;++i)printf("%d ",seq[i]);puts("");
        long long dis;
        for(i=end;i>=1;--i){
            dis=calc(seq[i],Anc[seq[i]]);
            if(IsImp.ask(seq[i],nowv))f.modify(Anc[seq[i]],dis,nowv);else f.modify(Anc[seq[i]],min(dis,f.ask(seq[i],nowv)),nowv);
        }
        print(f.ask(1,nowv));
    }
    return Final(),0;
}


Tags: LCA单调性 树形dp
Posted in BZOJ | 0 Comments