参考博客：
每次对当前联通块get_root,以rt为根dfs计算经过当前rt的答案，然后把rt设为不可通过的障碍，就把子树分为了若干联通块，递归下去对每一个联通块也这样做。
最多递归log层，每一层的节点数都是O(n)。时间复杂度O(nlogn)。
//Achen#include#include #include #include #include #include #include #include const int K=10000007,N=10007,M=100;typedef long long LL;using namespace std;int n,m,nsz,rt,qs[M],bo[K],ok[N];template void read(T &x) { char ch=getchar(); x=0; T f=1; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int ecnt,fir[N],nxt[N<<1],to[N<<1],val[N<<1];void add(int u,int v,int w) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w; nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w;}int sz[N],vis[N],mxsz[N],dis[N],sta[N],tp;void dfs(int x,int fa,int top) { for(int i=1;i<=m;i++) if(qs[i]>=dis[x]&&bo[qs[i]-dis[x]]==top) ok[i]=1; for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa&&!vis[to[i]]) { sta[++tp]=to[i]; dis[to[i]]=dis[x]+val[i]; dfs(to[i],x,top); if(x==top) { while(tp) { int y=sta[tp--]; bo[dis[y]]=top; } } }}void get_root(int x,int fa) { sz[x]=1; mxsz[x]=0; for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa&&!vis[to[i]]){ get_root(to[i],x); sz[x]+=sz[to[i]]; mxsz[x]=max(mxsz[x],sz[to[i]]); } mxsz[x]=max(mxsz[x],nsz-sz[x]); if(!rt||mxsz[x]
用刚才一模一样的方法。为了不统计一个子树里的路径，访问rt的一个子树是就把子树里的点全部暴力压进栈里，访问完了再更新rt的答案，然而比容斥跑得快些。
//Achen#include#include #include #include #include #include #include #include const int N=20007;typedef long long LL;using namespace std;int n,nsz,rt,up,dn;template void read(T &x) { char ch=getchar(); x=0; T f=1; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int gcd(int a,int b) { return !b?a:gcd(b,a%b); }int ecnt,fir[N],nxt[N<<1],to[N<<1],val[N<<1];void add(int u,int v,int w) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w; nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w;}int sz[N],vis[N],mxsz[N],dis[N],sta[N],tp,bo[3];void dfs(int x,int fa,int top) { if(x==top) up+=bo[(3-dis[x])%3]; else up+=bo[(3-dis[x])%3]*2; sz[x]=1; for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa&&!vis[to[i]]) { sta[++tp]=to[i]; dis[to[i]]=(dis[x]+val[i])%3; dfs(to[i],x,top); sz[x]+=sz[to[i]]; if(x==top) { while(tp) { int y=sta[tp--]; bo[dis[y]]++; } } }}void get_root(int x,int fa) { sz[x]=1; mxsz[x]=0; for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa&&!vis[to[i]]){ get_root(to[i],x); sz[x]+=sz[to[i]]; mxsz[x]=max(mxsz[x],sz[to[i]]); } mxsz[x]=max(mxsz[x],nsz-sz[x]); if(!rt||mxsz[x]
之前写的容斥的版本，感觉很不优秀啊。
//Twenty#include#include #include #include #include #include #include #include const int maxn=20000+299;int ecnt,fir[maxn],nxt[maxn*2],to[maxn*2],val[maxn*2],vis[maxn],root,n; int ans,f[5],sz[maxn],mx[maxn],sum,dis[maxn];using namespace std;int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}void add(int u,int v,int w){ nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w%3; nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w%3;}void dfs(int x,int fa){ f[dis[x]]++; for(int i=fir[x];i;i=nxt[i]){ int v=to[i]; if(vis[v]||v==fa) continue; dis[v]=(dis[x]+val[i])%3; dfs(v,x); }}int cul(int x,int d){ dis[x]=d; f[0]=f[1]=f[2]=0; dfs(x,0); return f[0]*f[0]+f[1]*f[2]*2;}void get_root(int x,int fa){ sz[x]=1; mx[x]=0; for(int i=fir[x];i;i=nxt[i]){ int v=to[i]; if(v==fa||vis[v]) continue; get_root(v,x); sz[x]+=sz[v]; mx[x]=max(mx[x],sz[v]); } mx[x]=max(mx[x],sum-sz[x]); if(mx[x]