[BZOJ1316]树上的询问点分治-白红宇

[BZOJ1316]树上的询问点分治

阅读量：5230 次

发布时间：2019-06-14

本文共 1978 字，大约阅读时间需要 6 分钟。

1316: 树上的询问

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 1017 Solved: 287

[][][]

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

Sample Output

Yes

HINT

30%的数据，n≤100．

100%的数据，n≤10000，p≤100，长度≤1000000．

做完此题可看下POJ 3237 Tree

Source

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define maxn 100000 8 using namespace std; 9 int n,q;10 int ask[maxn];11 int ans[maxn];12 struct edge {13 int to,next,c;14 }e[maxn*2];15 int head[maxn],cnt;16 void add(int u,int v,int c){e[cnt].to=v;e[cnt].next=head[u];e[cnt].c=c;head[u]=cnt++;}17 int root;18 int vis[maxn],size[maxn],sum,f[maxn];19 void findrt(int x,int fa) {20 size[x]=1;f[x]=0;21 for(int i=head[x];i>=0;i=e[i].next) {22 int to=e[i].to;if(to==fa||vis[to]) continue;23 findrt(to,x);24 size[x]+=size[to];25 f[x]=max(f[x],size[to]);26 }27 f[x]=max(f[x],sum-size[x]);28 if(f[x]
            
             =0;i=e[i].next) {34 int to=e[i].to;if(to==fa||vis[to]) continue;35 dfs(to,x,d+e[i].c);36 }37 }38 void cal(int x,int fl,int d) {39 tt=0;tmp=0;40 dfs(x,0,d);41 sort(dis+1,dis+tt+1);42 for(int i=1;i<=tt;i++) {43 if(dis[i]!=dis[i-1]||i==1) dis[++tmp]=dis[i],num[tmp]=1;44 else num[tmp]++;45 }46 for(int i=1;i<=q;i++) {47 for(int j=1;j<=tmp;j++)48 if(num[j]>=2&&dis[j]*2==ask[i]) ans[i]+=fl*num[j]*(num[j]-1);49 int l=1,r=tmp;50 while(l
             
              ask[i]&&l
              
               =0;i=e[i].next) {63 int to=e[i].to;if(vis[to]) continue;64 cal(to,-1,e[i].c);65 root=0;sum=size[to];findrt(to,x);66 work(root);67 }68 }69 int main() {70 memset(head,-1,sizeof(head));71 scanf("%d%d",&n,&q);72 for(int i=1;i
               
                0||!ask[i]) printf("Yes\n");83 else printf("No\n");84 }