题目链接

  其实这题用Set就完事了但我不会Set

  智商-=inf

  求虚树上所有边权和的两倍。

  具体方式就是splay把所有在虚树上的点存一下,(按照DFS序排序的)每次插入/删除会更新前驱和它、后继和它、前驱和后继的值

  

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstdlib>
#include<map>
#define maxn 200020
using namespace std;
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} struct Splay{
struct Node{
int e[],fa;long long val,size;
}tree[maxn];
int root,tot;
Splay(){ root=tot=; }
inline int iden(int x){ return x==tree[tree[x].fa].e[]; }
inline void connect(int x,int fa,int how){ tree[x].fa=fa; tree[fa].e[how]=x; }
inline void update(int x){ tree[x].size=tree[tree[x].e[]].size+tree[tree[x].e[]].size+; }
void rotate(int x){
int y=tree[x].fa; int r=tree[y].fa;
int sony=iden(x); int sonr=iden(y);
if(root==y) root=x;
int b=tree[x].e[sony^];
connect(b,y,sony);
connect(y,x,sony^);
connect(x,r,sonr);
update(y); update(x);
}
void splay(int pos,int to){
to=tree[to].fa;
while(tree[pos].fa!=to){
if(tree[tree[pos].fa].fa==to) rotate(pos);
else
if(iden(tree[pos].fa)==iden(pos)){ rotate(tree[pos].fa),rotate(pos); }
else {rotate(pos),rotate(pos); }
}
}
inline int create(int fa,int val){
tree[++tot]=(Node){{,},fa,val,};
return tot;
}
inline int build(int val){
if(root==){
root=create(,val);
return root;
}
int now=root;
while(now){
tree[now].size++;
int nxt=val<tree[now].val?:;
if(tree[now].e[nxt]==){
connect(create(now,val),now,nxt);
return tot;
}
now=tree[now].e[nxt];
}
}
inline void insert(int val){
int p=build(val);
splay(p,root);
}
inline int find(int val){
int now=root;
while(now){
if(tree[now].val==val) return now;
int nxt=val<tree[now].val?:;
now=tree[now].e[nxt];
}
return ;
}
void dele(int x){
tree[x].e[]=tree[x].e[]=;
if(x==tot) tot--;
}
void pop(int val){
int now=find(val);
if(now==) return;
splay(now,root);
if(tree[now].e[]==){
root=tree[now].e[];
tree[root].fa=;
dele(now);
return;
}
int deal=tree[now].e[];
while(tree[deal].e[]) deal=tree[deal].e[];
splay(deal,tree[now].e[]);
connect(tree[now].e[],deal,);
root=deal; tree[deal].fa=;
update(deal);
dele(now);
return;
}
inline int lower(int val){
int now=root,ans=-0x7fffffff;
while(now){
if(tree[now].val<val&&tree[now].val>ans) ans=tree[now].val;
int nxt=val<tree[now].val?:;
now=tree[now].e[nxt];
}
return ans;
}
inline int upper(int val){
int now=root,ans=0x7fffffff;
while(now){
if(tree[now].val>val&&tree[now].val<ans) ans=tree[now].val;
int nxt=val<tree[now].val?:;
now=tree[now].e[nxt];
}
return ans;
}
}s; int d[maxn][];
long long w[maxn][];
int dfn[maxn],ID;
int deep[maxn];
bool ext[maxn];
int back[maxn];
long long dis[maxn]; struct Edge{
int next,to;
long long val;
}edge[maxn*];
int head[maxn],num;
inline void add(int from,int to,long long val){
edge[++num]=(Edge){head[from],to,val};
head[from]=num;
} void find(int x,int fa){
dfn[x]=++ID; back[ID]=x;
deep[x]=deep[fa]+;
for(int i=head[x];i;i=edge[i].next){
int to=edge[i].to;
if(to==fa) continue;
dis[to]=dis[x]+edge[i].val;
d[to][]=x; w[to][]=edge[i].val;
find(to,x);
}
return;
} long long calcdis(int x,int y,int opt){
long long ans=;
if(deep[x]<deep[y]) swap(x,y);
int f=deep[x]-deep[y];
for(int i=;(<<i)<=f;++i)
if(f&(<<i)){
ans+=w[x][i];
x=d[x][i];
}
if(x==y) return opt==?ans:x;
for(int i=;i>=;--i){
if(d[x][i]==d[y][i]) continue;
ans+=w[x][i]+w[y][i];
x=d[x][i]; y=d[y][i];
}
return opt==?ans+w[x][]+w[y][]:d[x][];
} int main(){
int n=read(),m=read();
for(int i=;i<n;++i){
int from=read(),to=read(),val=read();
add(from,to,val);
add(to,from,val);
}
find(,);
for(int j=;j<=;++j)
for(int i=;i<=n;++i){
d[i][j]=d[d[i][j-]][j-];
w[i][j]=w[i][j-]+w[d[i][j-]][j-];
}
long long ans=;
while(m--){
int e=read();
int dfe=dfn[e];
if(ext[e]==){
ext[e]=;
int low=s.lower(dfe),upp=s.upper(dfe);
if(low>) ans+=calcdis(back[low],e,);
if(upp<=n) ans+=calcdis(back[upp],e,);
if(low>&&upp<=n) ans-=calcdis(back[low],back[upp],);
s.insert(dfe);
}
else{
ext[e]=;
s.pop(dfe);
int low=s.lower(dfe),upp=s.upper(dfe);
if(low>) ans-=calcdis(back[low],e,);
if(upp<=n) ans-=calcdis(back[upp],e,);
if(low>&&upp<=n) ans+=calcdis(back[low],back[upp],);
}
int last=s.lower(n+),first=s.upper();
long long ret=;
if(last>&&first<=n){ int lca=calcdis(back[last],back[first],);
ret=dis[back[last]]+dis[back[first]]-*dis[lca];
}
printf("%lld\n",ans+ret);
}
return ;
}

最新文章

  1. ABP理论学习之验证DTO
  2. Hololens开发笔记之连接PC实现资源共享
  3. QT学习之路--菜单、工具条、状态栏
  4. HTML5 新特性总结
  5. Android优化——UI检视利器:Hierarchy Viewer
  6. try catch finally执行顺序
  7. 转载 shell sort
  8. atoi、stoi、strtoi区别
  9. 封装cookie组件
  10. 树莓派玩耍笔记4 -- 树莓派ssh党必备的配置
  11. java Pattern和Matcher详解
  12. EventEmitter:nodeJs事件触发机制
  13. 使用sparksql往kafka推送数据
  14. Redhat6.5——解决yum功能不能正常使用
  15. Qt 之 模态、非模态、半模态窗口的介绍及 实现QDialog的exec()方法
  16. 三张图搞懂JavaScript的原型对象与原型链 / js继承,各种继承的优缺点(原型链继承,组合继承,寄生组合继承)
  17. English trip EM2-LP-1B Favorite Things Teacher:William Full name: Willian Richard Ogzrd 威廉理查德&#183;奥格兹德
  18. 看看用PS来转基因的动物,居然很欢乐!!
  19. 阿里云centos7.2 lamp配置
  20. maven中的snapshot来源与注意事项

热门文章

  1. hdu-1068&amp;&amp;POJ1466 Girls and Boys---最大独立集
  2. 扫描局域网ip的shell
  3. 【CF799B】T-shirt buying(一道很水的小根堆)
  4. Problem G: 圆周率
  5. python 线程even
  6. 2018年ElasticSearch6.2.2教程ELK搭建日志采集分析系统(目录)
  7. flask-bootstrap
  8. 多页应用 Webpack4 配置优化与踩坑记录
  9. confirm() 方法用于显示一个带有指定消息和 OK 及取消按钮的对话框。系统自带提示
  10. JZOJ 3487. 【NOIP2013模拟联考11】剑与魔法(dragons)