wubaiting2020 @ 2019-10-05 17:31:50
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f,MAXX=100005;
int read()
{
int s=0,bj=0;
char ch=getchar();
while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return bj?-s:s;
}
void printnum(int x)
{
if(x>9)printnum(x/10);
putchar(x%10^48);
}
void print(int x,char ch)
{
if(x<0){putchar('-');x=-x;}
printnum(x);putchar(ch);
}
struct node{int nx,to,v;}w[200005];int cnt,h[100005];
void AddEdge(int x,int y,int z){w[++cnt].to=y;w[cnt].nx=h[x];w[cnt].v=z;h[x]=cnt;}
int size[100005],son[100005],vst[100005],sum,maxx,tot,root,dis[100005],ans[2000005];//son[]子树中的最大节点数
int n,m;
void GR(int x,int fa)
{
size[x]=1;son[x]=0;
for(int i=h[x];i;i=w[i].nx)
{
int y=w[i].to;
if(y^fa&&!vst[y])
{
GR(y,x);//向下递归求解
size[x]+=size[y];
son[x]=max(son[x],size[y]);//更新
}
son[x]=max(son[x],sum-size[x]);//除了这一半子树的另一半子树
if(son[x]<maxx)root=x,maxx=son[x];
}
}
void Dis(int x,int fa,int no)
{
dis[++tot]=no;
for(int i=h[x];i;i=w[i].nx)
{
int y=w[i].to;
if(y^fa&&!vst[y])Dis(y,x,no+w[i].v);
}
}
void cal(int x,int bj,int len)
{
tot=0;Dis(x,-1,len);
for(int i=1;i<tot;i++)
for(int j=i+1;j<=tot;j++)
if(bj)ans[dis[i]+dis[j]]++;
else ans[dis[i]+dis[j]]--;
}
void solve(int x)
{
cal(x,1,0);vst[x]=1;//就算答案，标记已访问
for(int i=h[x];i;i=w[i].nx)
{
int y=w[i].to;
if(!vst[y])
{
cal(y,0,w[i].v);//容斥减去重复状态
maxx=INF;sum=size[y];root=0;GR(y,-1);//算出在子树y中的重心
solve(root);
}
}
}
int main()
{
int x,y,z;
n=read();m=read();
for(int i=1;i<n;i++)
{
x=read();y=read();z=read();
AddEdge(x,y,z);AddEdge(y,x,z);
}
sum=n;maxx=INF;GR(1,-1);solve(root);
for(int i=1;i<=m;i++)
{
x=read();
if(ans[x]>0)puts("AYE");
else puts("NAY");
}
return 0;
}
by Soledad_S @ 2019-10-06 13:08:23
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f,MAXX=100005;
int read()
{
int s=0,bj=0;
char ch=getchar();
while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return bj?-s:s;
}
void printnum(int x)
{
if(x>9)printnum(x/10);
putchar(x%10^48);
}
void print(int x,char ch)
{
if(x<0){putchar('-');x=-x;}
printnum(x);putchar(ch);
}
struct node{int nx,to,v;}w[200005];int cnt,h[100005];
void AddEdge(int x,int y,int z){w[++cnt].to=y;w[cnt].nx=h[x];w[cnt].v=z;h[x]=cnt;}
int size[100005],son[100005],vst[100005],sum,maxx,tot,root,dis[100005],ans[2000005];//son[]子树中的最大节点数
int n,m;
void GR(int x,int fa)
{
size[x]=1;son[x]=0;
for(int i=h[x];i;i=w[i].nx)
{
int y=w[i].to;
if(y^fa&&!vst[y])
{
GR(y,x);//向下递归求解
size[x]+=size[y];
son[x]=max(son[x],size[y]);//更新
}
}
son[x]=max(son[x],sum-size[x]);//除了这一半子树的另一半子树
if(son[x]<maxx)root=x,maxx=son[x];
}
void Dis(int x,int fa,int no)
{
dis[++tot]=no;
for(int i=h[x];i;i=w[i].nx)
{
int y=w[i].to;
if(y^fa&&!vst[y])Dis(y,x,no+w[i].v);
}
}
void cal(int x,int bj,int len)
{
tot=0;Dis(x,-1,len);
for(int i=1;i<tot;i++)
for(int j=i+1;j<=tot;j++)
if(bj)ans[dis[i]+dis[j]]++;
else ans[dis[i]+dis[j]]--;
}
void solve(int x)
{
cal(x,1,0);vst[x]=1;//就算答案，标记已访问
for(int i=h[x];i;i=w[i].nx)
{
int y=w[i].to;
if(!vst[y])
{
cal(y,0,w[i].v);//容斥减去重复状态
maxx=INF;sum=size[y];root=0;GR(y,-1);//算出在子树y中的重心
solve(root);
}
}
}
int main()
{
int x,y,z;
n=read();m=read();
for(int i=1;i<n;i++)
{
x=read();y=read();z=read();
AddEdge(x,y,z);AddEdge(y,x,z);
}
sum=n;maxx=INF;GR(1,-1);solve(root);
for(int i=1;i<=m;i++)
{
x=read();
if(ans[x]>0)puts("AYE");
else puts("NAY");
}
return 0;
}by Soledad_S @ 2019-10-06 13:08:54
@wubaiting2020 已A，自己找哪个脑残地方写错了
by wubaiting2020 @ 2019-10-06 13:56:52
艹 @Soledad 感谢奆奆……