Tree
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 20098 | Accepted: 6608 |
Description
Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k. Write a program that will count how many pairs which are valid for a given tree.
Input
The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l. The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
题意：给一颗带权树，求树上长度不超过L的路径条数
首先有一个有树高限制时的树形DP做法..........
对于一条树路径 只有经过或不经过一个点的情况
考虑经过一个点的路径，可以由其他点到它的两条路径拼出来
对于不经过的情况 把一棵树按这个点拆成好几棵分治
每次对于当前子树选择树的重心，最多递归logn次，而每层最多只有n个点(每层的所有子树组成整棵树)，复杂度O(logn*处理每层的复杂度)
过程：
1.求重心
2.处理经过当前点的路径
3.对子树分治
每次分治的各个子树是互不影响的，vis[i]表示i这个点已经分治过了
注意：既然你的写法是先找重心在递归，那么一定要rt=0;dfsRt(v,0);dfsSol(rt);是rt啊啊啊啊啊不是v了
对于本题，处理经过点u的路径时，先dfs子树中所有点对深度，排序两个指针往里扫计算<=L的，在减去在同一颗子树里的(同样计算)
总复杂度O(nlog^2n)
#include#include #include #include using namespace std;const int N=10005,INF=1e9+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int n,L,u,v,w;struct edge{ int v,w,ne;}e[N<<1];int h[N],cnt;inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;}int size[N],d[N],vis[N],root,sum;void dfsRoot(int u,int fa){ size[u]=1;d[u]=0; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(vis[v]||v==fa) continue; dfsRoot(v,u); size[u]+=size[v]; d[u]=max(d[u],size[v]); } d[u]=max(d[u],sum-size[u]); if(d[u]
还有一种做法，用treap维护，考虑经过每个点的路径时，建一颗treap维护长度，每个点加上之前遍历过的这点的子树中<L-deep[v]+1的，最后再把这棵子树的所有深度加入treap
//// main.cpp// treap//// Created by Candy on 2017/1/9.// Copyright ? 2017年 Candy. All rights reserved.//#include#include #include #include #include using namespace std;#define lc t[x].l#define rc t[x].rconst int N=1e5+5,INF=1e9;int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){ if(c=='-')f=-1; c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();} return x*f;}struct node{ int l,r,v,w,size,rnd;}t[N];int sz,root;inline void update(int x){t[x].size=t[lc].size+t[rc].size+t[x].w;}inline void lturn(int &x){ int c=rc;rc=t[c].l;t[c].l=x; t[c].size=t[x].size;update(x);x=c;}inline void rturn(int &x){ int c=lc;lc=t[c].r;t[c].r=x; t[c].size=t[x].size;update(x);x=c;}void ins(int &x,int v){ if(x==0){ x=++sz; t[x].l=t[x].r=0; t[x].v=v;t[x].w=t[x].size=1; t[x].rnd=rand(); return; } t[x].size++; if(v==t[x].v) t[x].w++; else if(v