直接点分治, 用平衡树(set就行了...)维护.
-------------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<set>
using namespace std;
typedef long long ll;
const int maxn = 10009;
const int maxm = 109;
int read() {
char c = getchar();
int ret = 0;
for(; !isdigit(c); c = getchar());
for(; isdigit(c); c = getchar()) ret = ret * 10 + c - '0';
return ret;
}
struct edge {
int to, w;
edge* next;
} E[maxn << 1], *pt = E, *head[maxn];
void AddEdge(int u, int v, int w) {
pt->to = v; pt->w = w; pt->next = head[u]; head[u] = pt++;
}
int n, Rt, Min, size[maxn];
int N, qn;
ll q[maxm];
bool ans[maxm], vis[maxn];
set<ll> Bst;
void init() {
N = read(); qn = read();
for(int i = 1; i < N; i++) {
int u = read() - 1, v = read() - 1, w = read();
AddEdge(u, v, w);
AddEdge(v, u, w);
}
for(int i = 0; i < qn; i++)
scanf("%lld", q + i);
n = N;
}
void dfs(int x, int fa) {
size[x] = 1;
int Max = 0;
for(edge* e = head[x]; e; e = e->next) if(e->to != fa && !vis[e->to]) {
dfs(e->to, x);
size[x] += size[e->to];
Max = max(size[e->to], Max);
}
Max = max(Max, n - size[x]);
if(Max < Min)
Min = Max, Rt = x;
}
void Insert(int x, int fa, ll w) {
Bst.insert(w);
for(edge* e = head[x]; e; e = e->next) if(!vis[e->to] && fa != e->to)
Insert(e->to, x, w + e->w);
}
void update(int x, int fa, ll w) {
for(int i = 0; i < qn; i++) if(!ans[i])
ans[i] |= (Bst.find(q[i] - w) != Bst.end());
for(edge* e = head[x]; e; e = e->next) if(!vis[e->to] && fa != e->to)
update(e->to, x, w + e->w);
}
void solve(int x) {
Min = maxn;
dfs(x, -1);
x = Rt;
Bst.clear();
Bst.insert(0);
for(edge* e = head[x]; e; e = e->next) if(!vis[e->to]) {
update(e->to, x, e->w);
Insert(e->to, x, e->w);
}
vis[x] = true;
for(edge* e = head[x]; e; e = e->next) if(!vis[e->to]) {
n = size[e->to];
solve(e->to);
}
}
int main() {
init();
memset(vis, 0, sizeof vis);
memset(ans, 0, sizeof ans);
solve(0);
for(int i = 0; i < qn; i++)
if(!q[i]) ans[i] = true;
for(int i = 0; i < qn; i++)
puts(ans[i] ? "Yes" : "No");
return 0;
}
-------------------------------------------------------------------------------------
1316: 树上的询问
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 417 Solved: 103
[Submit][Status][Discuss]
Description
一棵n个点的带权有根树，有p个询问，每次询问树中是否存在一条长度为Len的路径，如果是，输出Yes否输出No.
Input
第一行两个整数n, p分别表示点的个数和询问的个数． 接下来n-1行每行三个数x, y, c，表示有一条树边x→y，长度为c． 接下来p行每行一个数Len，表示询问树中是否存在一条长度为Len的路径．
Output
输出有p行，Yes或No.
Sample Input
6 4
1 2 5
1 3 7
1 4 1
3 5 2
3 6 3
1
8
13
14
1 2 5
1 3 7
1 4 1
3 5 2
3 6 3
1
8
13
14
Sample Output
Yes
Yes
No
Yes
Yes
No
Yes
HINT
30%的数据，n≤100．
100%的数据，n≤10000，p≤100，长度≤1000000．
做完此题可看下POJ 3237 Tree