这两天在看虚树,的确很难理解。

不过大致的思路就是说删掉一些没有用的点,但是仍然保持树的相对结构,树上只有两种点,一个是集合点,和一些LCA,这些LCA是为了保持树的相对结构,才留下的。

具体做法网上说的天花乱坠,我实在是想吐槽。作为新人没有什么很好的入门资料,大佬们也是含含糊糊,就是一顿套模板了(和图论一样),反正做题也是在新树上重新DP~~~

附上BZOJ2286的模板例子,我删减了一部分。根据题意来~~~

具体的原理我也不想管了。ヾ(◍°∇°◍)ノ゙  who care who 呢?

#include<iostream>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<stack>
#define inf 1e60
#define pa pair<int,int>
#define ll long long
using namespace std; int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} int bin[];
int n,m,cnt,ind,top;
int last[],last2[],fa[][];
ll mn[],f[];
int h[],mark[],deep[];
int st[]; struct edge{
int to,next,v;
}e[],ed[]; void insert(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
} void insert2(int u,int v) //单向边了,也可以是双向的。
{ if(u==v)return;
printf("%d--->%d\n",u,v);
ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;
} bool cmp(int a,int b)
{
return mark[a]<mark[b];
} void pre(int x)
{
mark[x]=++ind;
for(int i=;bin[i]<=deep[x];i++)
fa[x][i]=fa[fa[x][i-]][i-];
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa[x][])
{
mn[e[i].to]=min(mn[x],(ll)e[i].v);
deep[e[i].to]=deep[x]+;
fa[e[i].to][]=x;
pre(e[i].to);
}
} int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=;bin[i]<=t;i++)
if(t&bin[i])x=fa[x][i];
for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if(x==y)return x;
return fa[x][];
} void dp(int x)
{
f[x]=mn[x];
ll tmp=;
for(int i=last2[x];i;i=ed[i].next)
{
dp(ed[i].to);
tmp+=f[ed[i].to];
}
last2[x]=;
if(tmp==)f[x]=mn[x];
else if(tmp<=f[x])f[x]=tmp;
} void solve()
{
cnt=;
int K=read();
for(int i=;i<=K;i++)
h[i]=read();
sort(h+,h+K+,cmp);
int tot=K;
// h[++tot]=h[1];
// for(int i=2;i<=K;i++) {
// int tmp = lca(h[tot],h[i]);
// if(lca(h[tot],h[i])!=h[tot])
// h[++tot]=h[i];
// } st[++top]=; //top栈指针
for(int i=;i<=tot;i++)
{
int now=h[i],f=lca(now,st[top]);
while()
{
if(deep[f]>=deep[st[top-]])
{
insert2(f,st[top--]);
if(st[top]!=f)st[++top]=f;
break;
}
insert2(st[top-],st[top]);top--;
}
if(st[top]!=now)st[++top]=now;
} while(--top)insert2(st[top],st[top+]);
dp();
printf("%lld\n",f[]);
} int main()
{
freopen("in.txt","r",stdin);
bin[]=;for(int i=;i<;i++)bin[i]=bin[i-]<<;
n=read();
for(int i=;i<n;i++)
{
int u=read(),v=read(),w=read();
insert(u,v,w);
}
mn[]=inf;pre();
m=read();
for(int i=;i<=m;i++)
solve();
return ;
}

最近两天的训练效果不咋样,心思太杂了,我得调整调整,好好A题吧~~~

具体方案就是看论文,做经典题吧~~~

详细论文:

2015集训队论文集

《浅谈字符串匹配的几种方式》

《后缀数组》

《后缀自动机及其应用》

《生成函数的运用与组合计数问题》

2016集训队论文

《网络流的一些建模方法》

《再探快速傅里叶变换》

DP专题:

http://www.cnblogs.com/qscqesze/p/4614733.html

最新文章

  1. Java03
  2. Centos安装完MariaDB后启动不了 MySQL is not running, but lock file (/var/lock/subsys/mysql) exists
  3. 40免费的 jQuery &amp; CSS3 图片热点特效
  4. /usr/include/gnu/stubs.h:7:27: error: gnu/stubs-32.h:No such file or directory的解决办法
  5. Windows Phone 8.1SDK新特性预览
  6. [转]日期格式化(yyyy-MM-dd)中,为什么 M 多大写?
  7. 15_采用Pull解析器解析和生成XML内容
  8. codeforces 676A A. Nicholas and Permutation(水题)
  9. delphi 操作 TWebBrowser 实现自动填表(JQuery脚本与 OleVariant 方法)
  10. Java的数据类型和参数传递
  11. SimpleDateFormat安全的时间格式化
  12. vscode C++开发环境配置教程(教你如何用vscode写C++)
  13. no module named win32api
  14. Go used as value问题
  15. Swift搭建本地http服务器,实现外部视频即时播放
  16. 关于java Collections.sort 排序
  17. 纯C++安卓开发 (ndk)系列之 ---- 常见问题
  18. python面向对象(类的成员及类方法)
  19. python re示例
  20. [SoapUI] Mock Service

热门文章

  1. IOS下去掉input submit圆角和背景色错误
  2. IDEA 中tomcat启动问题时,一直出去发布状态,无法加载项目
  3. Linux私房菜阅读笔记
  4. (转)浅谈千万级PV/IP规模高性能高并发网站架构
  5. 请求网络图片缓存到本地 ,还有一些现成的图片加载框架的使用 Ace网络篇(一)
  6. 使用windows的BitLocker+VHD加密“文件夹”
  7. python实现excel转json的例子
  8. 数组和json的相互转换
  9. 移动端本地 H5 秒开方案探索与实现
  10. Python快速入门_1