我们对于一棵树,我们找一个根,然后统计过这个点的路径有多少符合要求。怎么搞呢?我们可以先维护一个数据结构,然后把先把根作为一个距离自己为0的点放进去,然后对于每一棵子树,先找出所有的与之前的数据结构的东西进行统计,然后放入数据结构,递归每一棵子树,就可以搞了。为了保证复杂度,所以每一次选重心提起来。还是比较好些,然后我写的splay就莫名的慢,想快的可以写treap之类的(' '     )

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; typedef long long ll;
const ll maxn = ;
const ll INF = 0x3f3f3f3f; struct node {
ll data, weight, size;
node *son[], *fa;
}e[maxn]; ll ne = ;
node* root; void update(node* x) {
x-> size = x-> weight;
for(ll i = ; i < ; ++ i) {
if(x-> son[i]) x-> size += x-> son[i]-> size;
}
} void rotate(node *x, ll f) {
node* t = x-> fa;
if(t-> fa) {
if(t-> fa-> son[] == t) t-> fa-> son[] = x;
else t-> fa-> son[] = t;
}
x-> fa = t-> fa, x-> size = t-> size, t-> fa = x;
t-> son[f] = x-> son[!f];
if(x-> son[!f]) x-> son[!f]-> fa = t;
x-> son[!f] = t;
update(t);
} void splay(node* x, node* f) {
while(x-> fa != f) {
if(x-> fa-> fa == f) {
ll a = x-> fa-> son[] == x ? : ;
rotate(x, a);
}
else {
node* t = x-> fa, *r = t-> fa;
ll a = r-> son[] == t ? : ;
ll b = t-> son[] == x ? : ;
if(a == b) rotate(t, a), rotate(x, b);
else rotate(x, b), rotate(x, a);
}
}
if(x-> fa == NULL) root = x;
} node* newnode(ll v) {
node* x = e + ne ++;
x-> data = v, x-> size = x-> weight = ;
x-> son[] = x-> son[] = NULL;
return x;
} void insert(ll v) {
node* x = root;
while(x) {
x-> size ++;
if(x-> data == v) {
x-> weight ++;
splay(x, NULL); break;
}
else {
ll a = x-> data > v ? : ;
if(x-> son[a]) x = x-> son[a];
else {
x-> son[a] = newnode(v);
x-> son[a]-> fa = x;
splay(x-> son[a], NULL);
break;
}
}
}
if(!x) root = newnode(v), root-> fa = NULL;
} ll work(ll v) {
node *x = root; ll ret = ;
while(x) {
if(x-> data <= v) {
ret += x-> weight + (x-> son[] ? x-> son[]-> size : );
x = x-> son[];
}
else x = x-> son[];
}
return ret;
} struct edge {
ll t, d;
edge* next;
}se[maxn * ], *head[maxn]; ll oe = ;
ll n, m, a[maxn], top = ;
ll s[maxn], stop = ; void addedge(ll f, ll t, ll d) {
se[oe].t = t, se[oe].d = d, se[oe].next = head[f], head[f] = se + oe ++;
} bool vis[maxn]; ll size[maxn], dis[maxn]; void dfs(ll x, ll fa) {
size[x] = ; s[++ stop] = x;
for(edge* p = head[x]; p; p = p-> next) if(p-> t != fa && !vis[p-> t]) dfs(p-> t, x), size[x] += size[p-> t];
} void find_dis(ll x, ll fa) {
a[++ top] = x;
for(edge* p = head[x]; p; p = p-> next) {
if(!vis[p-> t] && p-> t != fa) dis[p-> t] = dis[x] + p-> d, find_dis(p-> t, x);
}
} ll int_get() {
ll x = ; char c = (char)getchar(); bool f = ;
while(!isdigit(c) && c != '-') c = (char)getchar();
if(c == '-') c = (char)getchar(), f = ;
while(isdigit(c)) {
x = x * + (int)(c - '');
c = (char)getchar();
}
if(f) x = -x;
return x;
} void read() {
n = int_get();
for(ll i = ; i <= n - ; ++ i) {
ll u, v, w; u = int_get(), v = int_get(), w = int_get();
addedge(u, v, w), addedge(v, u, w);
}
m = int_get();
} ll ans = ; void sov(ll x) {
stop = ;
dfs(x, ); ll tot = size[x];
if(tot == ) return;
ll Max = INF, pos = x;
for(ll j = ; j <= stop; ++ j) {
ll i = s[j];
ll tmax = ;
for(edge* p = head[i]; p; p = p-> next) if(!vis[p-> t] && size[x] > size[p-> t]) tmax = max(tmax, size[p-> t]);
tmax = max(tot - size[i], tmax);
if(Max > tmax) Max = tmax, pos = i;
}
ll rt = pos; root = NULL; ne = ;
insert();
for(edge* p = head[rt]; p; p = p-> next) {
if(!vis[p-> t]) {
top = , dis[p-> t] = p-> d, find_dis(p-> t, rt);
for(ll i = ; i <= top; ++ i) ans += work(m - dis[a[i]]);
for(ll i = ; i <= top; ++ i) insert(dis[a[i]]);
}
}
vis[rt] = ;
for(edge* p = head[rt]; p; p = p-> next) {
if(!vis[p-> t]) sov(p-> t);
}
} int main() {
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
read();
memset(vis, , sizeof(vis));
sov();
printf("%lld\n", ans);
return ;
}

最新文章

  1. 缩放因子和UI设计
  2. Bootstrap自带的一些预定义的按钮颜色
  3. 命令行下使用javah命令生成.h文件,出现“错误: 无法访问android.app.Activity 找不到android.app.Activity的类文件”的解决方法
  4. Sqlserver 原生 MD5 函数(转)
  5. B - Frogger
  6. spring03autowire属性
  7. Primes on Interval(二分 + 素数打表)
  8. 简单的JQuery top返回顶部
  9. table中的换行问题
  10. libvirt学习
  11. java web基础 --- URL重定向Filter
  12. python unittest 测试笔记(二):使用Requests
  13. DOM-----style属性对照表
  14. Activity、Fragment、Dialog基类简单整理
  15. 我的 OneNote 入门心得
  16. sqlserver2017 重装过程中出现“无法找到数据库引擎启动句柄”错误的解决办法
  17. 网关绑定命令,解决arp攻击
  18. 使用kbmMW#1轻松实现REST
  19. 解决部分小程序无法获取UnionId的问题
  20. 转:oracle:win7手工卸载oracle数据库11g

热门文章

  1. Cloudera Hadoop启用Kerberos认证
  2. 【leetcode】1005. Maximize Sum Of Array After K Negations
  3. 【InnoDB】体系结构
  4. Python--nfs服务+计划任务crond服务+shell介绍
  5. element-ui弹窗实现自定义宽度
  6. [CSP-S模拟测试]:斯诺(snow)(数学+前缀和+树状数组)
  7. [NOIP模拟33]反思+题解
  8. flask中app.py: error: invalid choice: &#39;insert&#39;........的问题
  9. How do I force my .NET application to run as administrator?
  10. 二级域名解析设置及Apache 子域名配置