大意:给定树, 要求维护一个集合, 支持增删点, 询问从集合中任取一点作为起点, 遍历完其他点后原路返回的最短长度.

集合中的点按$dfs$序排列后, 最短距离就为$dis(s_1,s_2)+...+dis(s_k,s_1)$

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head #ifdef ONLINE_JUDGE
const int N = 1e6+10;
#else
const int N = 111;
#endif int n, m;
int sz[N], dep[N], fa[N];
ll w[N];
int son[N], top[N], L[N], R[N];
struct _ {int to,w;};
vector<_> g[N];
void dfs(int x, int f, int d) {
sz[x]=1,fa[x]=f,dep[x]=d,L[x]=++*L;
for (_ e:g[x]) if (e.to!=f) {
int y = e.to;
w[y]=w[x]+e.w;
dfs(e.to,x,d+1),sz[x]+=sz[y];
if (sz[y]>sz[son[x]]) son[x]=y;
}
}
void dfs(int x, int tf) {
top[x]=tf;
if (son[x]) dfs(son[x],tf);
for (_ e:g[x]) if (!top[e.to]) dfs(e.to,e.to);
}
int lca(int x, int y) {
while (top[x]!=top[y]) {
if (dep[top[x]]<dep[top[y]]) swap(x,y);
x = fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
ll dis(int x, int y) {return w[x]+w[y]-2*w[lca(x,y)];}
struct cmp {
bool operator () (const int & x, const int & y) const {
return L[x]<L[y];
}
};
set<int,cmp> s;
ll ans;
void solve(int x) {
int f = s.count(x)?-1:1;
if (f==1) s.insert(x);
auto t = s.lower_bound(x);
int L, R, A = *s.begin(), B = *--s.end();
if (s.size()==1) ;
else if (s.size()==2) {
if (x==A) ans+=2*f*dis(x,B);
else ans+=2*f*dis(A,x);
}
else {
if (x==B) L=*--t,R=A;
else if (x==A) L=B,R=*++t;
else L=*--t,R=*++++t;
ans += f*(dis(L,x)+dis(x,R)-dis(L,R));
}
if (f==-1) s.erase(x);
}
int main() {
scanf("%d%d", &n, &m);
REP(i,2,n) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].pb({v,w}),g[v].pb({u,w});
}
dfs(1,0,0),dfs(1,1);
REP(i,1,m) {
int x;
scanf("%d", &x);
solve(x);
printf("%lld\n", ans);
}
}

最新文章

  1. BZOJ2301: [HAOI2011]Problem b[莫比乌斯反演 容斥原理]【学习笔记】
  2. 如何解决google ping不通的问题。
  3. JAVA基于缓冲的文件读写操作
  4. ASP.NET读取配置文件发送邮件
  5. js 使用for循环遍历数组
  6. vijos 1115 火星人
  7. gunicorn 简介
  8. caoz大神力作、互联网从业者必读之书——《你凭什么做好互联网》深入总结
  9. laravel 服务容器
  10. 8.装饰模式(Decorator Pattern)
  11. 学习:MQTT协议及原理
  12. jmeter接口自动化部署jenkins教程
  13. Windows 下安装NPM
  14. Error 25007.初始化合成时发生错误。安装程序无法使用 LoadLibraryShim() 加载合成。
  15. win7取消任务栏预览并显示文件名
  16. 迷你MVVM框架 avalonjs 沉思录 第1节 土耳其开局
  17. 路由追踪:traceroute/tcptraceroute
  18. rabbitmq使用命令创建交换机、队列及绑定
  19. @Value关于static字段的注入
  20. [BZOJ 4033] 树上染色

热门文章

  1. Chrome 神器,神奇的技巧
  2. js上传图片获取原始宽高
  3. 0.JQuery学习
  4. 邻居子系统输出 之 neigh_output、neigh_hh_output
  5. 7 vi 编辑器
  6. 做一个把网页带出来的SpringBoot工程
  7. NodejS---require的机制
  8. 20 Django REST Framework 更改PUT/PATCH/DELETE的传参字段,默认为pk
  9. Flyway:数据库版本迁移工具的介绍
  10. java源码-Semaphore源码分析