Description
给一棵无根树，边有边权，每个点有两个权值 (d) 和 (w) ，分别表示那个点的最长被覆盖距离（就是必须有一个点在 (le d) 内有标记 ）和在该点打标记的代价
求让所有的点都被覆盖上的最小代价和
(n le 10^3)
Solution
这个题看到之后发现可以(O(n^2))预处理距离
（博主没有想到可以这么搞，还想着两个点转移的时候求 (LCA) ，那样复杂度还高）
定义状态为：
(f[i][j]) 表示 (i) 点被 (j) 点覆盖时，其子树都被覆盖的最小代价
(ans[i]) 表示 (i) 和它的子树的都被覆盖的最小代价
我们发现 (ans[i]) 就是 (f[i][]) 的 (min)
我们对于每一个点 (x) ，枚举那些可以覆盖它的点
每次找 (x) 的子节点， 用 (ans[son]) 求和转移就好了，但是需要考虑到的是这个覆盖 (x) 的点可能还能覆盖 (x) 的 儿子，所以要卡一下
最后 (ans) 找个 (min) 就行了
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=1010;
struct node{
int to,nxt,dis;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v,int w)
{
e[++cnt].dis=w; e[cnt].nxt=head[u]; e[cnt].to=v;
return head[u]=cnt,void();
}
int w[N],d[N],n,dis[N][N],ans[N],f[N][N];
bool vis[N];
inline void spfa(int s)
{
memset(vis,0,sizeof(vis));
queue<int> q; q.push(s); dis[s][s]=0; vis[s]=1;
while(!q.empty())
{
int fr=q.front(); q.pop();
for(int i=head[fr];i;i=e[i].nxt)
{
int t=e[i].to;
int dist=dis[s][fr]+e[i].dis;
if(!dis[s][t]&&!vis[t])
{
dis[s][t]=dist;vis[t]=1;
q.push(t);
}
}
} return ;
}
inline void dfs(int x,int fat)
{
for(int i=head[x];i;i=e[i].nxt)
{
if(e[i].to!=fat) dfs(e[i].to,x);
}
for(int i=1;i<=n;++i)
{
if(dis[x][i]>d[x]){f[x][i]=1e15+10; continue;}
int sum=0;
for(int j=head[x];j;j=e[j].nxt)
{
int t=e[j].to; if(t==fat) continue;
sum+=min(ans[t],f[t][i]-w[i]);
} f[x][i]=sum+w[i];
}
for(int i=1;i<=n;++i) ans[x]=min(ans[x],f[x][i]);
return ;
}
inline void work()
{
memset(f,0,sizeof(f)); memset(ans,0x3f,sizeof(ans));
memset(dis,0,sizeof(dis)); memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); cnt=0;
n=read();
for(int i=1;i<=n;++i) w[i]=read();
for(int i=1;i<=n;++i) d[i]=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read(),w=read();
add(u,v,w); add(v,u,w);
}
for(int i=1;i<=n;++i) spfa(i);
dfs(1,0);
cout<<ans[1]<<endl;
return ;
}
signed main()
{
int T=read();
while(T--) work();
return 0;
}
}
signed main(){return yspm::main();}
这代码会在 (POJ) 上超时，但是正确性是可以保证的
Review
在想不到怎么在线好写的时候就可以想怎么离线预处理啥的整一下
而且分块思考如果距离想不出来就先想转移，不要卡部分