点分治
点分治的例题2（本题代码结果为TLE……）
强烈谴责卡时限QAQ，T了无数次啊无数次……
不过在N次的静态查错中倒是加深了对点分治的理解……也算因祸得福吧（自我安慰一下）
TLE后的改进：每棵子树在重算f数组的时候，不要完全清空，而是清到最深深度即可。——>WA
//SPOJ 1825
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
inline void read(int &v){
v=; int sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
v*=sign;
}
/******************tamplate*********************/
const int N=,INF=1e8;
int n,m,k,root=,h[N],s[N],g[N],f[N],size,d[N];
bool vis[N],black[N];
int to[N],head[N],next[N],len[N],tot=;
inline void ins(int x,int y,int l){
to[++tot]=y; next[tot]=head[x]; head[x]=tot; len[tot]=l;
to[++tot]=x; next[tot]=head[y]; head[y]=tot; len[tot]=l;
} inline void getroot(int x,int fa){
s[x]=;h[x]=;
for(int i=head[x];i;i=next[i])
if (to[i]!=fa && !vis[to[i]]){
getroot(to[i],x);
s[x]+=s[to[i]];
//h[x]=max(h[x],s[to[i]]);
if (s[to[i]]>h[x]) h[x]=s[to[i]];
}
h[x]=max(h[x],size-s[x]);
if (h[x]<h[root]) root=x;
} inline void getdep(int x,int fa){
int res=;
for(int i=head[x];i;i=next[i]){
if (to[i]!=fa && !vis[to[i]]){
d[to[i]]=d[x]+black[to[i]];
getdep(to[i],x);
res=max(res,d[to[i]]);
}
}
d[x]+=res;
}
inline void getg(int x,int fa,int leng,int c){
g[c]=max(g[c],leng);
for(int i=head[x];i;i=next[i])
if (to[i]!=fa && !vis[to[i]]) getg(to[i],x,leng+len[i],c+black[to[i]]);
}
struct node{int deep,to,len;}st[N];
inline bool cmp(const node &a,const node &b) {return a.deep<b.deep;}
int ans=,cnt; void getans(int x){
vis[x]=;
for(int i=head[x];i;i=next[i])
getdep(to[i],x);
cnt=;
F(i,,n) f[i]=;
for(int i=head[x];i;i=next[i]){
if (!vis[to[i]]){
d[to[i]]=black[to[i]];
getdep(to[i],x);
st[cnt++]=(node){d[to[i]],to[i],len[i]};
}
}
sort(st,st+cnt,cmp);
rep(i,cnt){
int y=st[i].to;
F(j,,d[y]) g[j]=-INF;
getg(y,x,st[i].len,black[y]);
if (i>){
int end=min(k-black[x],d[y]);
F(j,,end){
int p=min(d[st[i-].to],k-j-black[x]);
if (f[p]==-INF) break;
if (g[j]!=-INF) ans=max(ans,g[j]+f[p]);
}
}
F(j,,d[y]){
f[j]=max(f[j],g[j]);
if (j) f[j]=max(f[j],f[j-]);
if (j+black[x]<=k) ans=max(ans,f[j]);
}
} for(int i=head[x];i;i=next[i])
if (!vis[to[i]]){
root=; size=s[to[i]];
getroot(to[i],x);
getans(root);
}
} int main(){
// freopen("1825.in","r",stdin);
read(n); read(k); read(m);
int x,y,l;
F(i,,m){ read(x); black[x]|=;}
F(i,,n){
read(x); read(y); read(l);
ins(x,y,l);
}
root=; size=n; h[root]=INF;
getroot(,);
getans(root);
printf("%d\n",ans);
return ;
}
WA：deep要反过来求，d[x]表示以x为根的子树中黑点最长的路径（而不是从root到x经过了多少黑点）
虽然好像原来的求法也能做不过不如这个方便（我一开始是写成两种混合了……QAQ）
RE:数组不能开20W，我改了个40W过了QAQ【iwtwiioi：双向边当然要开两倍的边集】！！！
//SPOJ 1825
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
inline void read(int &v){
v=; int sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
v*=sign;
}
/******************tamplate*********************/
const int N=,INF=1e8;
int n,m,k,root=,h[N],s[N],g[N],f[N],size,d[N];
bool vis[N],black[N];
int to[N],head[N],next[N],len[N],tot=;
inline void ins(int x,int y,int l){
to[++tot]=y; next[tot]=head[x]; head[x]=tot; len[tot]=l;
to[++tot]=x; next[tot]=head[y]; head[y]=tot; len[tot]=l;
} inline void getroot(int x,int fa){
s[x]=;h[x]=;
for(int i=head[x];i;i=next[i])
if (to[i]!=fa && !vis[to[i]]){
getroot(to[i],x);
s[x]+=s[to[i]];
//h[x]=max(h[x],s[to[i]]);
if (s[to[i]]>h[x]) h[x]=s[to[i]];
}
h[x]=max(h[x],size-s[x]);
if (h[x]<h[root]) root=x;
} inline void getdep(int x,int fa){
int res=;
s[x]=; d[x]=black[x];
for(int i=head[x];i;i=next[i]){
if (to[i]!=fa && !vis[to[i]]){
getdep(to[i],x);
res=max(res,d[to[i]]);
s[x]+=s[to[i]];
}
}
d[x]+=res;//x为根的子树的最大“深度”
}
inline void getg(int x,int fa,int leng,int c){
g[c]=max(g[c],leng);
for(int i=head[x];i;i=next[i])
if (to[i]!=fa && !vis[to[i]])
getg(to[i],x,leng+len[i],c+black[to[i]]);
} inline bool cmp(int x,int y){
return d[to[x]]<d[to[y]];
}
int ans=,st[N],cnt; inline void getans(int x){
vis[x]=;//vis=1保证递归搜索子树时不会搜到当前节点
//对根的出边按dep排序
cnt=;
for(int i=head[x];i;i=next[i]){
if (!vis[to[i]]){
getdep(to[i],x);
st[cnt++]=i;
}
}
sort(st,st+cnt,cmp);
F(i,,d[to[st[cnt-]]]) f[i]=-INF;
rep(i,cnt){
int y=to[st[i]];
F(j,,d[y]) g[j]=-INF;
getg(y,x,len[st[i]],black[y]);
if (i>){
int end=min(k-black[x],d[y]);
F(j,,end){
int p=min(d[to[st[i-]]],k-j-black[x]);
if (f[p]==-INF) break;//!!!这里没懂
if (g[j]!=-INF) ans=max(ans,g[j]+f[p]);
}
}
F(j,,d[y]){
f[j]=max(f[j],g[j]);
if (j) f[j]=max(f[j],f[j-]);
if (j+black[x]<=k) ans=max(ans,f[j]);
}
} for(int i=head[x];i;i=next[i])
if (!vis[to[i]]){
root=; size=s[to[i]];
getroot(to[i],x);
getans(root);
}
} int main(){
#ifndef ONLINE_JUDGE
freopen("1825.in","r",stdin);
#endif
read(n); read(k); read(m);
int x,y,l;
F(i,,m){ read(x); black[x]|=;}
F(i,,n){
read(x); read(y); read(l);
ins(x,y,l);
}
root=; size=n; h[root]=INF;
getroot(,);
getans(root);
printf("%d\n",ans);
return ;
}
调了一天半终于出来了！锻炼了耐心和静态查错能力～