Aimee

这是个dp？不过没有必要用dp

毕竟显然距离为2中间一定要经过一个点，那枚举中间点即可

之后显然假设一个点所有相邻的点的点权为集合$A= { a_1,a_2,a_3······a_k}$

显然对于这个点，和就是$sum{1}^{i=k} sum{1}^{j=k} a_i*a_j |i！=j$

那么这样上面的那个式子显然等于$(sum_{1}^{i=k}ai)^2-sum{1}^{i=k}a_i^2$

这样的话就能以一个可行的复杂度解决问题了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int u,v;
const int maxn=200001;
const int maxm=200001;
int w[maxn];
int head[maxn];
int p;
struct b{
    int to;
    int ne;
}ed[maxm*2];
void add(int f,int t){
    p++;
    ed[p].to=t;
    ed[p].ne=head[f];
    head[f]=p;
    return ;
}
int znx;
int ans;
int mod=10007;
int max1,max2;
int sin;
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&w[i]);
    }
    for(int i=1;i<=n;++i){
        int Archie=0;
        int Aimee=0;
        max1=0;
        max2=0;
        for(int j=head[i];j;j=ed[j].ne){
            int v=w[ed[j].to];
            Archie=(Archie+v)%mod;
            Aimee=(Aimee+v*v)%mod;
            if(v>max1){
                max2=max1;
                max1=v;
            }else{
                if(v>max2){
                    max2=v;
                }
            }
        }
        ans=(ans+(Archie*Archie)%mod-Aimee)%mod;
        sin=max(sin,max1*max2); 
    }
    cout<<sin<<" "<<(ans+mod)%mod;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map> 
using namespace std;
int x[4];
char a,b;
int f;
int ma[5][5][5];
int dp[201][201][5];
map <char,int> m; 
map <int,char> mm;
string s;
int org[201];
int ff;
bool find(int l,int r,int aim,int mid){
    ff=0;
    for(int i=0;i<=3;++i){
        for(int j=0;j<=3;++j){

            if(dp[l][mid][i]&&dp[mid+1][r][j]){
                if(ma[i][j][aim])
                ff=1;
            }
        }
    }
    return ff;
}
int main(){
    m['W']=0;
    m['I']=1;
    m['N']=2;
    m['G']=3;
    mm[0]='W';
    mm[1]='I';
    mm[2]='N';
    mm[3]='G';
    for(int i=0;i<4;++i){
        scanf("%d",&x[i]); 
    } 
    for(int i=0;i<=3;++i){
        for(int j=1;j<=x[i];++j){
            cin>>a>>b;
            ma[m[a]][m[b]][i]=1;
        }
    }
    cin>>s;
    int l=s.length();
    for(int i=0;i<l;++i){
        int j=i+1;
        org[j]=m[s[i]];
        dp[j][j][m[s[i]]]=1;
    }
    for(int i=2;i<=l;++i){
        for(int j=1;(j+i-1)<=l;++j){
            int r=j+i-1;
            for(int k=0;k<=3;++k){
                for(int z=j;z<r;++z){
                    if(find(j,r,k,z)){
                        dp[j][r][k]=1;
                    }
                }
            }
        }
    }
    for(int i=0;i<=3;++i){
        if(dp[1][l][i]){
            cout<<mm[i];
            f=1;
        }
    }
    if(!f){
        cout<<"The name is wrong!";
    }
    return 0;
}