点分治

  1 //SPOJ 1825  2 #include<cstdio>  3 #include<cstring>  4 #include<cstdlib>  5 #include<iostream>  6 #include<algorithm>  7 #define rep(i,n) for(int i=0;i<n;++i)  8 #define F(i,j,n) for(int i=j;i<=n;++i)  9 #define D(i,j,n) for(int i=j;i>=n;--i) 10 using namespace std; 11 inline void read(int &v){ 12     v=0; int sign=1; char ch=getchar(); 13     while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();} 14     while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();} 15     v*=sign; 16 } 17 /******************tamplate*********************/ 18 const int N=200010,INF=1e8; 19 int n,m,k,root=0,h[N],s[N],g[N],f[N],size,d[N]; 20 bool vis[N],black[N]; 21 int to[N],head[N],next[N],len[N],tot=0; 22 inline void ins(int x,int y,int l){ 23     to[++tot]=y; next[tot]=head[x]; head[x]=tot; len[tot]=l; 24     to[++tot]=x; next[tot]=head[y]; head[y]=tot; len[tot]=l; 25 } 26  27 inline void getroot(int x,int fa){ 28     s[x]=1;h[x]=0; 29     for(int i=head[x];i;i=next[i]) 30         if (to[i]!=fa && !vis[to[i]]){ 31             getroot(to[i],x); 32             s[x]+=s[to[i]]; 33             //h[x]=max(h[x],s[to[i]]); 34             if (s[to[i]]>h[x]) h[x]=s[to[i]]; 35         } 36     h[x]=max(h[x],size-s[x]); 37     if (h[x]<h[root]) root=x; 38 } 39  40 inline void getdep(int x,int fa){ 41     int res=0; 42     for(int i=head[x];i;i=next[i]){ 43         if (to[i]!=fa && !vis[to[i]]){ 44             d[to[i]]=d[x]+black[to[i]]; 45             getdep(to[i],x); 46             res=max(res,d[to[i]]); 47         } 48     } 49     d[x]+=res; 50 } 51 inline void getg(int x,int fa,int leng,int c){ 52     g[c]=max(g[c],leng); 53     for(int i=head[x];i;i=next[i]) 54         if (to[i]!=fa && !vis[to[i]]) getg(to[i],x,leng+len[i],c+black[to[i]]); 55 } 56 struct node{int deep,to,len;}st[N]; 57 inline bool cmp(const node &a,const node &b) {return a.deep<b.deep;} 58 int ans=0,cnt; 59  60 void getans(int x){ 61     vis[x]=1; 62     for(int i=head[x];i;i=next[i]) 63         getdep(to[i],x); 64     cnt=0; 65     F(i,0,n) f[i]=0; 66     for(int i=head[x];i;i=next[i]){ 67         if (!vis[to[i]]){ 68             d[to[i]]=black[to[i]]; 69             getdep(to[i],x); 70             st[cnt++]=(node){d[to[i]],to[i],len[i]}; 71         } 72     } 73     sort(st,st+cnt,cmp); 74     rep(i,cnt){ 75         int y=st[i].to; 76         F(j,0,d[y]) g[j]=-INF; 77         getg(y,x,st[i].len,black[y]); 78         if (i>0){ 79             int end=min(k-black[x],d[y]); 80             F(j,0,end){ 81                 int p=min(d[st[i-1].to],k-j-black[x]); 82                 if (f[p]==-INF) break; 83                 if (g[j]!=-INF) ans=max(ans,g[j]+f[p]); 84             } 85         } 86         F(j,0,d[y]){ 87             f[j]=max(f[j],g[j]); 88             if (j) f[j]=max(f[j],f[j-1]); 89             if (j+black[x]<=k) ans=max(ans,f[j]); 90         } 91     } 92      93     for(int i=head[x];i;i=next[i]) 94         if (!vis[to[i]]){ 95             root=0; size=s[to[i]]; 96             getroot(to[i],x); 97             getans(root); 98         } 99 }100 101 int main(){102 //    freopen("1825.in","r",stdin);103     read(n); read(k); read(m);104     int x,y,l;105     F(i,1,m){ read(x); black[x]|=1;}106     F(i,2,n){107         read(x); read(y); read(l);108         ins(x,y,l);109     }110     root=0; size=n; h[root]=INF;111     getroot(1,0);112     getans(root);113     printf("%d\n",ans);114     return 0;115 }