qndmx
by dbxxx @ 2020-03-11 13:47:57
~~QNDMX~~
by QiFeng233 @ 2020-03-11 13:57:01
~~**QNDMX**~~
by chen_03 @ 2020-03-11 14:22:44
$\mathbb{QNDMX}$
by chen_03 @ 2020-03-11 14:28:35
$\frak{QNDMX}$
by Aw顿顿 @ 2020-03-11 14:38:04
@[chen_03](/user/154520) Orz c03
by Lates @ 2020-03-11 14:38:17
@[Lates](/user/119062) 总觉得您的clac似乎常数大了点
试试双指针
by yama是女孩子 @ 2020-03-11 14:41:50
RE窝解释不清楚
by yama是女孩子 @ 2020-03-11 14:42:45
@[Lates](/user/119062) 你这样对每条路径都算一遍不TLE才怪
我的代码放这了，自己研究吧
```cpp
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAX_N=10005;
struct Edge
{
int v,w,nxt;
Edge(){}
Edge(int _v,int _w,int _nxt)
{
v=_v;
w=_w;
nxt=_nxt;
}
}E[MAX_N<<1];
int n,T;
int head[MAX_N];
int mx[MAX_N];
int siz[MAX_N];
bool used[MAX_N];
int q[MAX_N];
int ans[MAX_N];
int cnt=0;
void add_edge(int u,int v,int w)
{
E[cnt]=Edge(v,w,head[u]);
head[u]=cnt++;
}
void dfs_size(int v,int last)
{
siz[v]=1;
mx[v]=0;
for(int i=head[v];i!=-1;i=E[i].nxt)
{
int u=E[i].v;
if(u==last || used[u])continue;
dfs_size(u,v);
siz[v]+=siz[u];
mx[v]=max(mx[v],siz[u]);
}
}
int mi=1e9,rt=0;
void dfs_root(int idx,int v,int last)
{
mx[v]=max(mx[v],siz[idx]-siz[v]);
if(mx[v]<mi)
{
mi=mx[v];
rt=v;
}
for(int i=head[v];i!=-1;i=E[i].nxt)
{
int u=E[i].v;
if(u==last || used[u])continue;
dfs_root(idx,u,v);
}
}
int dist[MAX_N];
int top=0;
void dfs_dist(int v,int last,int dis)
{
dist[top++]=dis;
for(int i=head[v];i!=-1;i=E[i].nxt)
{
int u=E[i].v,w=E[i].w;
if(u==last || used[u])continue;
dfs_dist(u,v,dis+w);
}
}
const int MAX_L=1e7+5;
int mp[MAX_L];
void counting(int v,int dis,int flag)
{
top=0;
dfs_dist(v,0,dis);
int ret=0;
for(int i=0;i<top;i++)
{
for(int j=0;j<T;j++)
{
if(q[j]>=dist[i])ans[j]+=flag*mp[q[j]-dist[i]];
}
if(dist[i]<MAX_L)mp[dist[i]]++;
}
for(int i=0;i<top;i++)if(dist[i]<MAX_L)mp[dist[i]]--;
}
void solve(int v)
{
dfs_size(v,0);
mi=n;
dfs_root(v,v,0);
used[rt]=true;
counting(rt,0,1);
for(int i=head[rt];i!=-1;i=E[i].nxt)
{
int u=E[i].v,w=E[i].w;
if(used[u])continue;
counting(u,w,-1);
solve(u);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(head,-1,sizeof(head));
cnt=0;
cin>>n>>T;
for(int i=1;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
add_edge(u,v,w);
add_edge(v,u,w);
}
for(int i=0;i<T;i++)
{
int x;
cin>>x;
q[i]=x;
}
solve(1);
for(int i=0;i<T;i++)
{
if(ans[i])cout<<"AYE"<<endl;
else cout<<"NAY"<<endl;
}
return 0;
}
```
by Smile_Cindy @ 2020-03-11 14:43:18
@[Lates](/user/119062) 我的代码给您参考一下QwQ
```cpp
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std ;
const int MAXN = 1e4 + 10 , INF = 0x3f3f3f3f ;
int n , m , size[MAXN] , maxsize[MAXN] , cnt , r , rt , minn = INF ;
int dis[MAXN] , tmp[MAXN] , ans[MAXN] , q[MAXN] ;
bool vis[MAXN] ;
struct edge {
int to , cost ;
edge (int v = 0 , int w = 0) {to = v ; cost = w ;}
} ;
vector <edge> G[MAXN] ;
int R() {
int x = 0 ; char ch = getchar () ; bool f = 0 ;
for (; ch < 48 || ch > 57 ; ch = getchar ()) if (ch == '-') f = 1 ;
for (; ch >= 48 && ch <= 57 ; ch = getchar ()) x = (x << 1) + (x << 3) + (ch ^ 48) ;
return f ? -x : x ;
}
void findrt (int x , int fa) {
size[x] = 1 ; maxsize[x] = 0 ;
for (int i = 0 ; i < G[x].size () ; i++) {
int v = G[x][i].to ;
if (v == fa || vis[v]) continue ;
findrt (v , x) ;
size[x] += size[v] ;
if (size[v] > maxsize[x])
maxsize[x] = size[v] ;
}
if (cnt - size[x] > maxsize[x])
maxsize[x] = cnt - size[x] ;
if (maxsize[x] < minn) {
minn = maxsize[x] ;
rt = x ;
}
}
void getdis (int x , int fa) {
tmp[++r] = dis[x] ;
for (int i = 0 ; i < G[x].size () ; i++) {
int v = G[x][i].to , w = G[x][i].cost ;
if (v == fa || vis[v]) continue ;
dis[v] = dis[x] + w ;
getdis (v , x) ;
}
}
void query (int x , int w , int type) {
dis[x] = w ; r = 0 ;
getdis (x , 0) ;
sort (tmp + 1 , tmp + r + 1) ;
int l = 1 , tt = r ;
for (int i = 1 ; i <= m ; i++) {
l = 1 ; r = tt ;
while (l < r) {
if (tmp[l] + tmp[r] <= q[i]) ans[i] += type * (r - l) , l++ ;
else r-- ;
}
l = 1 ; r = tt ;
while (l < r) {
if (tmp[l] + tmp[r] < q[i]) ans[i] -= type * (r - l) , l++ ;
else r-- ;
}
}
}
void divide (int x) {
vis[x] = 1 ;
query (x , 0 , 1) ;
for (int i = 0 ; i < G[x].size () ; i++) {
int v = G[x][i].to , w = G[x][i].cost ;
if (vis[v]) continue ;
query (v , w , -1) ;
minn = INF ; rt = 0 ;
cnt = size[v] ;
findrt (v , 0) ;
divide (rt) ;
}
}
int main() {
n = R() ; m = R() ;
for (int i = 1 ; i < n ; i++) {
int u = R() , v = R() , w = R() ;
G[u].push_back (edge (v , w)) ;
G[v].push_back (edge (u , w)) ;
}
for (int i = 1 ; i <= m ; i++) q[i] = R() ;
cnt = n ;
findrt (1 , 0) ;
divide (rt) ;
for (int i = 1 ; i <= m ; i++) {
if (ans[i]) printf ("AYE\n") ;
else printf ("NAY\n") ;
}
return 0 ;
}
```
by yama是女孩子 @ 2020-03-11 14:44:52