《本题不卡常》，请求开大时限！！！

Morgen_Kornblume @ 2021-05-27 23:37:23

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<stdio.h>
#include<deque>
#include<cstring>
#include<map>
#include<utility>
using namespace std;
int n,m;
const int maxn=10010;
deque<pair<int,int> >que;
bool ans[110];
map<int,bool>mmp;

struct graph{
    int tot;
    int head[maxn],to[maxn],wei[maxn],nxt[maxn];
    int size;int root;int sub[maxn];int maxx;
    int dist[maxn];
    int sta[maxn];
    int top;
    int vis[maxn];

    void init(){
        tot=0;
        memset(head,0,sizeof(head));
    }

    void add(int x,int y,int z){
        tot++;
        nxt[tot]=head[x];
        head[x]=tot;
        to[tot]=y;
        wei[tot]=z;
    }

    void cul(int x,int fa){
        sta[++top]=dist[x];
        int opt=(int)que.size();
        for(int i=1;i<=opt;i++){
            pair<int,int>tmp=que.front();
            que.pop_front();
            if(ans[tmp.second])continue;
            if(tmp.first-dist[x]<0){
                que.push_back(tmp);continue;
            }
            if(mmp.find(tmp.first-dist[x])!=mmp.end()){
                ans[tmp.second]=true;
                continue;
            }
            que.push_back(tmp);
        }
        for(int i=head[x];i;i=nxt[i]){
            int go=to[i];
            if(vis[go]||go==fa){
                continue;
            }
            cul(go,x);
        }
    }

    void getroot(int x,int fa){
        sub[x]=1;
        int inmax=0;
        for(int i=head[x];i;i=nxt[i]){
            int go=to[i];
            if(vis[go]||go==fa){
                continue;
            }
            getroot(go,x);
            sub[x]+=sub[go];
            inmax=max(inmax,sub[go]);
        }
        inmax=max(inmax,size-sub[x]);
        if(inmax<maxx){
            maxx=inmax;
            root=x;
        }
    }

    void getdist(int x,int fa){

        for(int i=head[x];i;i=nxt[i]){
            int go=to[i];
            if(vis[go]||go==fa)continue;
            dist[go]=dist[x]+wei[i];
            getdist(go,x);
        }

    }

    void solve(int x){
        maxx=0x7fffffff;
        root=x;
        getroot(x,0);
        x=root;vis[x]=1;dist[x]=0;mmp.clear();
        getdist(x,0);
        mmp[0]=true;

        for(int i=head[x];i;i=nxt[i]){
            int go=to[i];
            if(vis[go])continue;
            cul(go,x);
            while(top)mmp[sta[top--]]=true;
        }

        for(int i=head[x];i;i=nxt[i]){
            int go=to[i];
            if(vis[go])continue;
            size=sub[go];
            solve(go);
        }
    }
}g;

int main(){
    que.clear();
    memset(ans,false,sizeof(ans));

    scanf("%d%d",&n,&m);

    int uu,vv,ww;
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&uu,&vv,&ww);
        g.add(uu,vv,ww);
        g.add(vv,uu,ww);
    }
    int tmp;
    for(int i=1;i<=m;i++){
        scanf("%d",&tmp);
        que.push_back(make_pair(tmp,i));
    }
    g.size=n;
    g.solve(1);

    for(int i=1;i<=m;i++){
        (ans[i])?(puts("AYE")):(puts("NAY"));
    }

    return 0;
}

by chen_qian @ 2021-05-28 11:06:23

@PY_Fighter 发出来康康。

by _lbw_ @ 2021-05-28 11:36:10

@PY_Fighter 发出来康康。

by PY_Fighter @ 2021-05-28 12:21:23

@chen_qian @lbw

#include<cstdio>
#include<algorithm>
#define N 2000005
using namespace std;
int n,k,num=0,head[N],d[N],siz[N],cnt=0;
bool vis[N];
struct node
{
    int v,w,nxt;
};
node e[N];
void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void dfs0(int u,int &g)
{
    siz[u]=1;vis[u]=true;
    for (int i=head[u];i;i=e[i].nxt)
    {
        if (!vis[e[i].v])
        {
            dfs0(e[i].v,g);
            if (siz[e[i].v]*2>n) g=e[i].v;
            siz[u]+=siz[e[i].v];
        }
    }
    vis[u]=false;
}
void getd(int u,int l)
{
    d[++num]=l;vis[u]=true;
    for (int i=head[u];i;i=e[i].nxt)
    {
        if (!vis[e[i].v]) getd(e[i].v,l+e[i].w);
    }
    vis[u]=false;
}
int calc(int u,int l)
{
    num=0;
    for (int i=1;i<=n;i++)
    d[i]=0;
    getd(u,0);
    sort(d+1,d+num+1);
    int i=1,j=num,sum=0;
    while (i<j)
    {
        if (d[i]+d[j]<=k-l) sum+=j-i++;
        else j--;
    }
    return sum;
}
int solve(int u)
{
    int g=u;
    dfs0(u,g);
    int ans=calc(g,0);
    vis[g]=true;
    for (int i=head[g];i;i=e[i].nxt)
    if (!vis[e[i].v])
    {
        ans-=calc(e[i].v,e[i].w<<1);
        ans+=solve(e[i].v);
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    int u,v,w;
    for (int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    scanf("%d",&k);
    printf("%d\n",solve(1));
    return 0;
}

这是Tree的代码

#include<cstdio>
#define N 2000005
using namespace std;
int cnt=0,head[N],siz[N],n,d[4];
bool vis[N];
struct node
{
    int v,w,nxt;
};
node e[N];
int gcd(int x,int y)
{
    if (!y) return x;
    return gcd(y,x%y);
}
void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void getg(int u,int &g)
{
    siz[u]=1;vis[u]=true;
    for (int i=head[u];i;i=e[i].nxt)
    if (!vis[e[i].v])
    {
        getg(e[i].v,g);
        if (siz[e[i].v]*2>n) g=e[i].v;
        siz[u]+=siz[e[i].v];
    }
    vis[u]=false;
}
void getd(int u,int l)
{
    d[l%3]++;vis[u]=true;
    for (int i=head[u];i;i=e[i].nxt)
    if (!vis[e[i].v]) getd(e[i].v,l+e[i].w);
    vis[u]=false;
}
int calc(int u,int k)
{
    for (int i=0;i<=3;i++)
    d[i]=0;
    getd(u,0);
    k%=3;
    if (k==0) return d[1]*d[2]+d[0]*(d[0]-1)/2;
    else if (k==1) return d[1]*(d[1]-1)/2+d[2]*d[0];
    else return d[2]*(d[2]-1)/2+d[1]*d[0];
}
int solve(int u)
{
    int g=u;
    getg(u,g);
    int ans=calc(g,0);
    vis[g]=true;
    for (int i=head[g];i;i=e[i].nxt)
    if (!vis[e[i].v])
    {
        ans-=calc(e[i].v,e[i].w<<1);
        ans+=solve(e[i].v);
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    int u,v,w;
    for (int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    int ans=solve(1)*2+n,s=n*n;
    int k=gcd(ans,s);
    printf("%d/%d\n",ans/k,s/k);
    return 0;
}

这是聪聪可可的代码